二叉树——中序遍历找位置

Question

我有一个二叉搜索树，我必须在其中实现一个名为

的方法

int valueAtPosition(int x)

问题是，我需要顺序遍历中的位置。

为了找到顺序遍历，我有以下代码，但我不知道如何计算递归调用，以获得正确的位置。

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

Answer 1

迭代中序遍历方法使这非常容易。每当从堆栈中弹出一个节点时，增加一个计数器。当计数器等于x时，return节点的值。

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); 
}

Answer 2

您也可以在递归方法中使用计数器。但是，您不能简单地传递一个 int counter 参数 - 您需要所有调用才能看到 "same" 计数器，因此您必须将它包装在 class 中（或者，如案例，一个内部 class):

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 个节点，它将 return null。如果您想改用基于 0 的索引，请将 { value--; return value == 0; } 更改为 { return value-- == 0; }

Answer 3

以下为递归中序遍历方式：(in c++)

bool valueAtPositionUtil(struct treeNode *root, int &currIndex, int i, int &value) {
    if(root != NULL) {
        if(valueAtPositionUtil(root->left, currIndex, i, value)) {
            return true;
        }
        if(currIndex == i) {
            value = root->data;
            return true;
        }
        currIndex++;
        if(valueAtPositionUtil(root->right, currIndex, i, value)) {
            return true;
        }
    }
    return false;
}

int ValueAtPosition(int i, struct treeNode *root) {
    int value = 0;
    int currIndex = 0;
    if(valueAtPositionUtil(root, currIndex, i, value)) {
        return value;
    }
    //index out of bound
    // you can return according your problem
    return -1; 
}

Answer 4

我认为其他解决方案都是 O(n)。您所需要的只是 O(log n) 的每个节点的 children 计数。

当您插入一个节点时，对于您遍历的每个节点，您将遍历的节点上的计数器增加一个。

您需要在删除、重新平衡等操作时维护这些计数器，这通常并不困难。

这样就可以获取节点插入时的位置，按值查找节点位置或按位置查找节点。

按位置查找节点与按值查找是同一种二进制遍历。如果你想要位置 1000 的项目，那么你从根开始。没有根，不是那个位置的项目。然后你看左边child（你也可以换个顺序，然后切换ascending/descending），左边如果左边child存在child的个数左边的 ren 是 0 加上左边节点 children 的计数。假设在这种情况下，左边存在并且有 500 children。那你就知道1000留不下了，因为左边的东西不够了，所以一定是右边的。您可以重复此操作，并一直向下检查边界。

对于简单的 O(n) 顺序遍历，如果你有一个全局计数器，你只需在遍历左侧后增加它。这应该与深度优先搜索相同。无需减少和增加计数器或在堆栈上推送和弹出。您还可以让函数 return 计数。

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

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

如果您还想 return 节点，这种方法只会变得烦人。

您当然可以用自己的堆栈替换递归函数，但这是很少需要的性能优化，如果您需要性能，则 O(log n) 解决方案比优化的自定义堆栈要好得多基于解决方案。

二叉树——中序遍历找位置

Binary tree - find position in inorder traversal

java

inorder

binary-search-tree