二叉树-在有序遍历中查找位置 [英] Binary tree - find position in inorder traversal

问题描述

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

I have a binary search tree where i have to implement a method called

int valueAtPosition(int x) 

问题是，我需要按顺序遍历该职位.

The problem is, that i need the position in an in order traversal.

要查找顺序遍历，我需要以下代码，但我不知道如何计算递归调用以获取正确的位置.

To find the in order traversal i have this the following code, but i don't know how i count the recursive calls, to get the right position.

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

推荐答案

您还可以在递归方法中使用计数器.但是，您不能简单地传递int counter参数-您需要进行所有调用才能看到相同"计数器，因此必须将其包装在一个类(或在这种情况下，是一个内部类)中:/p>

You can also use a counter in the recursive approach. However, you can't simply pass an int counter argument - you need all calls to see the "same" counter, so you will have to wrap it in a class (or, as in this case, an inner 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的索引)，您可以将其称为

To find the 9th node in-order (using 1-based indexing), you would call this as

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

如果没有 第9个节点，它将返回null.如果要改用基于0的索引，请将{ value--; return value == 0; }更改为{ return value-- == 0; }

If there is no 9th node, it would return null. If you want to use 0-based indexing instead, change { value--; return value == 0; } to { return value-- == 0; }

这篇关于二叉树-在有序遍历中查找位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！