1

と呼ばれるメソッドを実装する必要があるバイナリ検索ツリーがあります

int valueAtPosition(int x)

問題は、順序通りのトラバーサルで位置が必要なことです。

順番にトラバーサルを見つけるには、次のコードを使用しますが、再帰呼び出しを数えて正しい位置を取得する方法がわかりません。

public void inOrderTraverseTree(Node root){
    if(root != null){
        inOrderTraverseTree(root.leftChild);
        System.out.println(root);
        inOrderTraverseTree(root.rightChild); 
    }    
}
4

4 に答える 4

4

他の解決策はO(n)だと思います。これに必要なのは、O(log n) の各ノードの子の数だけです。

ノードを挿入すると、トラバースするノードごとに、トラバースしたノードのカウンターが 1 ずつ増えます。

通常は難しくない削除、再調整などの際にこれらのカウンターを維持する必要があります。

これにより、挿入時にノードの位置を取得したり、値でノードの位置を見つけたり、位置でノードを見つけたりできます。

位置によるノードの検索は、値による検索と同じ種類のバイナリ トラバーサルです。アイテムを 1000 の位置に配置したい場合は、ルートから開始します。その位置のルートではなく、アイテムではありません。次に、左の子を見てください (他の順序でも実行でき、昇順/降順を切り替えることができます)。左の子が存在する場合、左の子の数は 0 に左の子の数を加えたものです。ノード。このシナリオで、左派が存在し、500 人の子供がいるとします。次に、1000 は左側に十分なアイテムがないため、残すことができないことがわかります。したがって、1000 は正しいに違いありません。これを繰り返して、境界をずっとチェックすることもできます。

単純な O(n) のトラバーサルの場合、グローバル カウンターがある場合は、左にトラバースした後にのみ増加させます。これは、深さ優先検索と同じことを行う必要があります。カウンターを増減したり、スタックをプッシュしたりポップしたりする必要はありません。関数でカウントを返すようにすることもできます。

public int inOrderTraverseTree(Node root){
    if(root == null)
        return 0;

    int count = inOrderTraverseTree(root.leftChild);
    count++;
    count += inOrderTraverseTree(root.rightChild);
    return count;
}

このアプローチは、ノードも返したい場合にのみ面倒になります。

もちろん、再帰関数を独自のスタックに置き換えることもできますが、これはほとんど必要とされないパフォーマンスの最適化であり、パフォーマンスが必要な場合は、最適化されたカスタム スタック ベースのソリューションよりも O(log n) ソリューションの方がはるかに優れています。

于 2016-02-23T18:56:35.003 に答える
1

再帰的アプローチでカウンターを使用することもできます。ただし、単純に引数を渡すことはできませんint counter。「同じ」カウンターを表示するにはすべての呼び出しが必要なので、クラス (または、この場合は内部クラス) でラップする必要があります。

public static class Counter {
   private int value;
   public Counter(int initialValue) { value = initialValue; }
   public boolean decrement() { value--; return value == 0; }
   public boolean expired() { return value <= 0; }
}

public Node inOrderTraverseTree(Node root, Counter counter){
   if  (root != null && ! counter.expired()) {
       Node left = inOrderTraverseTree(root.leftChild, counter);
       if (left != null) {
            return left;
       } else if (counter.decrement()) {
            return root;
       } else {
            return inOrderTraverseTree(root.rightChild, counter); 
       }
   } else {
       return null;
   }
}

9 番目のノードを (1 ベースのインデックスを使用して) 順番に見つけるには、これを次のように呼び出します。

Node the9th = inOrderTraverseTree(root, new Counter(9));

9 番目のノードがない場合は、が返されnullます。代わりに 0 ベースのインデックスを使用する場合は、次のように変更{ value--; return value == 0; }します。{ return value-- == 0; }

于 2015-05-03T13:24:05.387 に答える
1

反復的な順序通りのトラバーサル アプローチにより、これは非常に簡単になります。ノードがスタックからポップされるたびにカウンターをインクリメントします。カウンターが x に等しい場合、ノードの値を返します。

Integer valueAtPosition(int x, Node root) {
  int count = 0;
  List<Node> stack = new ArrayList<>();
  Node node = root;
  while (!stack.isEmpty() || node != null) {
    if (node != null) {
      stack.add(node);
      node = node.leftChild;
    } else {
      node = stack.pop();
      if (count == x) {
        return node.value;
      }
      count++;
      node = node.rightChild;
    }
  }
  return null;
}

再帰バージョンでは、次のようにカウンターの変更可能なラッパーを渡す必要があります。

public class Counter {
   int count = 0;
}

public void inOrderTraverseTree(Node root, int index, Counter counter){
  if(root == null || counter.count > index) {
    return;
  }
  inOrderTraverseTree(root.leftChild);
  if (counter.count == index) {
    System.out.println(root);
  }
  counter.count = counter.count + 1;
  inOrderTraverseTree(root.rightChild); 
}
于 2015-05-03T12:53:33.487 に答える