如何在二叉树中找到第n个节点？

Question

我想在二叉树中找到第n个节点/元素。例如，不是第n个最大/最小，只是在顺序中的第n个。

怎么做？是否有可能将其保留为一个功能？许多函数使用外部变量来跟踪递归之外的迭代，但由于缺少更好的术语，这似乎是...懒惰。

Answer 1

您可以将二进制搜索树扩充为order statistic tree，它支持“返回第n个元素”操作

编辑：如果你只想要一个inorder遍历的第i个元素（而不是第i个最小元素）并且不想使用外部变量，那么你可以执行以下操作：

class Node {
  Node left
  Node right
  int data
}

class IterationData {
  int returnVal
  int iterationCount
}

IterationData findNth(Node node, IterationData data, int n) {
  if(node.left != null) {
    data = findNth(node.left, data, n)
  }
  if(data.iterationCount < n) {
    data.iterationCount++
    if(data.iterationCount == n) {
      data.returnVal = node.data
      return data
    } else if(node.right != null) {
      return findNth(node.right, data, n)
    } else {
      return data
    }
  }
}

你需要一些方法来返回两个值，一个用于迭代计数，一个用于返回值，一旦找到第n个节点;我已经使用了一个类，但是如果你的树包含整数，那么你可以使用带有两个元素的整数数组。

Answer 2

在迭代遍历中，跟踪在外部变量中传递的节点。

public static Node inOrderInterativeGet(Node root, int which){
    Stack<Node> stack = new Stack<Node>();
    Node current = root;
    boolean done = false;
    int i = 1;

    if(which <= 0){
        return null;
    }

    while(!done){
        if(current != null){
            stack.push(current);
            current = current.getLeft();
        }
        else{
            if(stack.empty()){
                done = true;
            }
            else{
                current = stack.pop();

                if(i == which){
                    return current;
                }
                i++;

                current = current.getRight();
            }
        }
    }

    return null;
}

Answer 3

如果您不喜欢全局变量，请传递给递归函数附加参数 - 一些int变量，让我们称之为auto_increment或只是ai。 ai存储当前节点的顺序。此外，递归函数应该返回当前顶点子树的ai的最大值，因为在访问整个子树后，下一个'free'值将是max_ai_in_subreee+1这样的东西

int rec(int vertex,int ai){
   traverseOrder[vertex] = ai
   if(getChildren(vertex)!=null) return ai;
   else{
     for(childrens){
         ai = rec(child,ai+1);
     }
     return ai;// subtree visited, return maximal free value upstairs.
   }
}

如果你的函数已经返回了一些有用的数据，它可能会返回一些包含{useful data+ai}的复杂对象

从一些顶点开始看起来像rec(start_vertex,1);

Answer 4

一种方法是使用一个size属性，即left_subtree + right_subtree + 1：

class Node:

    def __init__(self, data=None, left=None, right=None,
                 size=None):
        self.data = data
        self.left = left
        self.right = right
        self.size = size


def select(node, k):
  """Returns node with k-th position in-order traversal."""
  if not node:
    return None

  t = node.left.size if node.left else 0
  if t > k:
    return select(node.left, k)
  elif t < k:
    return select(node.right, k - t - 1)
  else:
    return node

Answer 5

下面是完整的代码，您可以使用它来在二叉树中使用inorder查找第n个元素。

public class NthNodeInInoeder {

    static public class Tree {

        public int data;
        public Tree left,right;

        public Tree(int data) {
            this.data = data;
        }
    }

    static Tree root;
    static int count = 0;

    private static void inorder(Tree root2, int num) {

        if (root2 == null)
            return;
        Tree node = root2;
        Stack<Tree> stack = new Stack<>();

        while (node != null || stack.size() > 0) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();
            count++;
            if (count == num) {
                System.out.println(node.data);
                break;
            }
            node = node.right;

        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        root = new Tree(10);
        root.left = new Tree(20);
        root.right = new Tree(30);
        root.left.left = new Tree(40);
        root.left.right = new Tree(50);
        int num = sc.nextInt();
        inorder(root, num);
        sc.close();

    }

}