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) 的每个节点的子节点计数。

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

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

有了这个，您可以在插入时获取节点的位置，按值查找节点的位置或按位置查找节点。

按位置查找节点与按值查找相同的二元遍历。如果您想要位置 1000 的项目，那么您从根开始。没有根，不是那个位置的项目。然后你看左边的孩子（你也可以按其他顺序做，并切换升序/降序），如果左边的孩子存在，左边的孩子的数量是0加上左边的孩子的数量节点。假设在这种情况下，左派存在并且有 500 个孩子。那么你知道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

迭代的有序遍历方法使这非常容易。每当从堆栈中弹出一个节点时增加一个计数器。当计数器等于 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 回答
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 回答
0

以下是递归中序遍历方法：（在 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; 
}
于 2015-05-03T14:24:19.530 回答