1

私は就職の面接のために勉強していて、木を見直していました、私はそれらを横断するときに問題はありませんが、私は正しい答えを見つけることができなかったという質問に行き着きました：

ルートノードへのポインタと、返したいノードのインオーダートラバーサル番号の2つのパラメータを指定して、ツリー内のノードを返す関数を記述します。ツリーに保存される唯一の情報は、各ノードの子の数です。

これまでのところ、ツリーに格納されている情報（子供の数）を気にする理由を理解することすらできませんでした。それ以外に、そのような木があると仮定した場合：

     5
  4     7
3  1  4

その場合、インオーダートラバーサルは次のようになります341547が、必要なノードを返すコードを理解できません（議論のために、インオーダートラバーサル番号は2であると想定しています。つまり、値1のノードが必要です）。

再帰的トラバーサルを実行しようとしましたが、最終的に内部カウンターをねじ込んでしまうため、別のアプローチを試し、すべてをスタックに配置しようとしましたが、正しく実行する方法がわかりません。これまでのところ：

public int findNode(root, position){
   Stack<Integer> s = new Stack<Integer>();
   cNode = root; //cNode = current Node

   while(cNode.left != null)
      cNode = cNode.left;

     s.push(cNode);

   while(cNode.right != null)
     cNode = cNode.right;

   //stuck here.
}

再帰的アプローチの方が簡単でしたが、探している＃があるかどうかを確認する方法がわかりません。

public int findNode(root, position){
    cNode = root;   
    if(cNode != null){ 
       findNode(cNode.left, position);
       System.out.print(cNode.data);
       findNode(cNode.right, position);
   }
}

私はこれが木を横断することを知っていますが、それでも私が望むことを正確には行いません。どんな助けでもいただければ幸いです。

4

4 に答える 4

1

あなたはそのようにすることができます： 

public Node findNode(Node root, int position) {
    ArrayList<Node> a = new ArrayList<Node>();
    populateNodes(root, a);
    return a.get(position);
}

private void populateNodes(Node node, ArrayList<Node> a) {
    if (node == null) return;
    populateNodes(node.left, a);
    a.add(node);
    populateNodes(node.right, a);
}

注: 不要な場合は、追加のデータ構造を使用する必要はありませんが、スタックがあったので、それを使用しました。

注 2: Jim Garrison が指摘したように、子孫の数があればアルゴリズムを最適化できます。

于 2012-02-01T21:34:48.063 に答える
1

質問があいまいです。「順序」は二分木にとって意味があります。この場合、「子孫の数」を意味しない限り、「子の数」は常に 2 です。この場合、順序リスト (O* n) 各ノードで、子孫の数に基づいてどの分岐を取るか (O*log n) を決定できるためです。

于 2012-02-01T20:34:50.493 に答える
0

各ノードが持っている子の総数を知っているツリーのプロパティを使用して、アルゴリズムの複雑さを軽減することをお勧めします。したがって、左側にいくつの子があるかがわかれば、現在のノードの順序番号を計算できます (ルートの場合、左側の子の数 + 1 になります)。次のコードは機能するはずです。

Nodeptr nthInInorder(Nodeptr root, int x){
 Nodeptr curr = root;
 int countedIn = 0, leftchildren = 0, currIn=0;

 while(curr!=NULL){
  if(curr->left == NULL)
   leftchildren = 0;
  else
   leftchildren = (curr->left)->data + 1;

  currIn = countedIn + leftchildren + 1;

  if(currIn == x)
   return curr;
  else if(currIn > x)
   curr = curr->left;
  else if(currIn < x)
   { countedIn = currIn + 1;
     curr = curr->right;
   }
  }
  return NULL;
 }

このアルゴリズムの複雑さは O(log n)

于 2013-01-27T20:06:28.600 に答える
0

位置を渡す代わりに、順序通りのトラバーサル番号を渡し、各再帰メソッドに追加します。

于 2012-02-01T20:35:42.940 に答える