1

多くの初心者と同じように、私の頭は再帰から吹き飛ばされます。SOに関する多くの回答/説明を調べました。しかし、私はまだコンセプトがはっきりしていません。(これは宿題ではありません。未学習のことを再学習しようとしていますが、再帰は文字列ポイントではありませんでした)

事前順序トラバーサルが与えられた場合、二分木を構築します。再帰では、一見単純でなければなりません:)しかし、私はそれを取得できません。

arr の順序は、ノードが挿入された順序でなければならないことがわかります。私を悩ませているのは：

  1. ノードにすでに左/右がある場合はどうなりますか? これはどのように作動しますか？

  2. 再帰はどのようにノードを挿入できますか?たとえば、次の事前順序で?

    12, 10, 6, 13

15 がルート、5、3、および左

10 の左の子として 6 を正しく挿入するにはどうすればよいですか?

    12
 10   13
6*

スケルトンコードは次のとおりです。

main()
{
   int[] arr = {};
   //make the first node a root node.
   node n = new node(arr[0]);
   buildbst(n, arr, 0)
}

buildbst(node root, int[] arr, int i)
{
   if (i == arr.length) return;

   if (arr[i] < root.data)
      root.left = new node (arr[i]);
   else
      root.right = new node(arr[i]);

   buildbst(root.left, arr, i++);
   buildbst(root.right, arr, i++);
}

編集：

再帰呼び出しを渡すと、buildbst(root.left, arr+i, i++) それが正しい方法であることに気付きましたか? それとも、私はこれに完全に間違ったアプローチをしていますか - 動的プログラミングと再帰と分割と征服の寄せ集め...

4

1 に答える 1

0

  1. 左/右の子を持つことはできません。あなたはそれをルートと呼びます。ルートには開始する子がありません。次に、左の子に対してそれを呼び出し、必要に応じて子を作成し、それらの子に対して関数を呼び出します。右に行くと、左の子に再びアクセスすることはなく、その子で呼び出された関数からノードに到達することはできません（再帰スタックを除いて、ツリーの上位に接続がないため）。

  2. これは与えられたときに起こるべきこと12, 10, 6, 13です：

    • ルートを作成します12
    • 呼び出しbuildbst(node(12), arr, 1)
      • 作成node(12).left = node(10)
      • 呼び出しbuildbst(node(10), arr, 2)
        • 作成node(10).left = node(6)
        • 呼び出しbuildbst(node(6), arr, 3)
          • 13 > 12、の正しい子である必要がある12ため、何もしないでください
        • 13 > 12、の正しい子である必要がある12ため、何もしないでください
      • 作成node(12).right = node(13)
      • 呼び出しbuildbst(node(13), arr, 3)
        • ほら、これ以上の要素はありません。これで完了です。

上記は2つの理由であなたのコードで起こることではありません：

  • コードは、左または右の子のいずれかのみを作成し、両方は作成しません（if-else））
  • コードにチェックがありませんmust be right child of '12'。これは少し複雑です。

以下のコードはそれをカバーするはずです。

node buildbst(int[] arr)
{
   node n = new node(arr[0]);
   // 9999999999 is meant to be > than the biggest element in your data
   buildbst(n, arr, 1, 9999999999);
   return node;
}

int buildbst(node current, int[] arr, int i, int biggestSoFar)
{
    if (i == arr.length) return i;

    // recurse left
    if (arr[i] < current.data)
    {
      current.left = new node(arr[i++]);
      i = buildbst(current.left, arr, i, current.data);
    }

    // recurse right
    if (i < arr.length && arr[i] < biggestSoFar)
    {
      current.right = new node(arr[i++]);
      i = buildbst(current.right, arr, i, biggestSoFar);
    }

    return i;
}

説明：

の目的は、次のbiggestSoFarことを防ぐことです。

    15                          15
   /                            /\
  5     versus (the correct)   5  20
 / \                          /
1   20                       1

たとえば、左から再帰する場合15、要素を取得したらすぐに要素の処理を停止する必要があります。> 15これは、を取得したときに発生します20。current.dataしたがって、より大きな値を取得した場合は、要素の処理を渡したり停止したりします。

5たとえば、から直接再帰する場合、要素を取得したらすぐに要素の処理を停止する必要があります。> 15これは、を取得したときに発生します20。biggestSoFarしたがって、より大きな値を取得した場合は、要素の処理を渡したり停止したりします。

于 2013-03-01T08:58:58.750 に答える