我有一个二叉搜索树在那里我必须实现一个名为方法
int valueAtPosition(int x)
问题是，我需要在序遍历在的位置。
为了找到在序遍历我有这个下面的代码，但我不知道我怎么算的递归调用，以获得正确的位置。
public void inOrderTraverseTree(Node root){
if(root != null){
inOrderTraverseTree(root.leftChild);
System.out.println(root);
inOrderTraverseTree(root.rightChild);
}
}
您也可以在递归方法使用一个计数器。 但是，你不能简单地传递一个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;
}
}
要找到（使用基于1的索引）中，订购9点，你会叫这个为
Node the9th = inOrderTraverseTree(root, new Counter(9));
如果没有 9号节点，它将返回null 。 如果你想使用基于0的索引代替，变化{ value--; return value == 0; } { value--; return value == 0; } { value--; return value == 0; }到{ return value-- == 0; } { return value-- == 0; }
我想其他的解决方案是为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）的解决方案，如果你需要的不仅仅是一个优化定制的基于堆栈的解决方案的性能。
迭代中序遍历方法使得这很容易。 递增每当一个节点从堆栈中弹出的计数器。 当计数器等于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);
}
以下是递归中序遍历方法：（用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;
}
