1

次の（奇妙な）方法で二分探索木を作成する必要があります。

配列 (A[n]) が与えられます。A[1] がツリーのルートになります。

  • 次に、ルートの左側のサブツリー (subtree1、以下で使用) に A[1]+A[2] を挿入し、ルートの右側のサブツリー (subtree2) に A[1]-A[2] を挿入します。

  • A[1]+A[2]+A[3] を subtree1 (subtree3) の左側のサブツリーに挿入し、A[1]+A[2]-A[3] を subtree1 (subtree4) の右側のサブツリーに挿入します。

  • 次に、A[1]-A[2]+A[3] を subtree2 の左側のサブツリー (subtree5) に挿入し、A[1]-A[2]-A[3] を subtree2 の右側のサブツリー (subtree6) に挿入します。 ）。

  • 配列の最後に到達するまで、subtree3、subtree4、subtree5、subtree6 について繰り返します。

したがって、基本的に、配列の最初の要素がツリーのルートになり、次に下に移動します。すべての左側のサブツリーには、その親と配列の次の要素の合計が値として含まれ、すべての右側のサブツリーには、次の値の差がありますその親および配列内の次の要素の。

再帰の概念を使用する必要があることは理解していますが、変更された方法で使用します。ここに私の問題を入力して、私の脳以外の誰かに説明しようとすると、実際に試してみるべきいくつかのアイデアが得られるような方法でそれを形成しましたが、私が扱っている問題は通常の問題であることがわかります。再帰を使用してツリーを構築する方法について、いくつかのヒントを教えてください。

他の質問や議論を見回してみると、全体的な解決策を求めることに対するポリシーがあることがわかっているので、解決策を求めているのではなく、それへのガイダンスを求めていることを明確にしたいと思いました. 誰かが見たいと思ったら、私がすでに行ったことをあなたに見せることができます.

4

1 に答える 1

0

再帰を行う方法は、すでに機能している関数が手元にあると常に想定することです。[Java構文を使用して]見てみましょう...

Tree buildTree(int currentSum, int[] array, int index, boolean sign);

それが機能するとします。次に、インデックス i でツリーを構築するために行う必要がありますか?

// current value to look at at this level
int curValue = array[index];
// depending on sign, it may be negative
if (!sign) { 
  curValue *= -1;
}
// add it to the running total
int nodeValue = currentSum + curValue;
Node nd = new Node(nodeValue);

nd.left = buildTree(nodeValue, array, index + 1, true);
nd.right = buildTree(nodeValue, array, index + 1, false);

基本的にはそれだけです。エッジケースに注意する必要があります: index = array.length、最初のノードの作成など

于 2011-03-24T01:27:33.360 に答える