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

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

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

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

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

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

按位置查找节点与按值查找是同一种二进制遍历。如果你想要位置 1000 的项目，那么你从根开始。没有根，不是那个位置的项目。然后你看看左边的 child (你也可以按其他顺序做，并切换升序/降序)，如果左边的 child 存在，左边的 child 数量为 0 加上左边 child 的数量节点。假设在这种情况下，左边存在并且有 500 个 child 。那你就知道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) 解决方案比优化的基于自定义堆栈的解决方案要好得多.