Java - 在 BT 的前序遍历中返回节点 x 之后访问的节点

Question

我被要求在 Java 中为学校“返回在二叉树的前序遍历中在节点 x 之后访问的节点”。我已经创建了一个代码来按预定顺序列出所有节点，但我不确定如何打印单个节点。

我创建节点的第一堂课是：

public class TreeNode {

int value;        // The data in this node.

TreeNode left;   // Pointer to the left subtree.

TreeNode right;  // Pointer to the right subtree.

TreeNode parent; //Pointer to the parent of the node. 

TreeNode(int value) {

    this.value = value;

    this.right = null;

    this.left = null;

    this.parent = null;

 }

 public void displayNode() { //Displays the value of the node.

    System.out.println(value + " ");

 }

然后我有班级来构建二叉树。它还按预定顺序打印整棵树：

public class BTree2 {

TreeNode root;                // the first node in the tree

public boolean isEmpty() // true if no links

{

    return root == null;

}

private TreeNode addRecursive(TreeNode current, int value) {

    if (current == null) {

        return new TreeNode(value);

    }

    if (value < current.value) {

        current.left = addRecursive(current.left, value);

    } else if (value > current.value) {

        current.right = addRecursive(current.right, value);

    } else {

        // value already exists

        return current;

    }

    return current;

}

public void add(int value) {

    root = addRecursive(root, value);

}

void printPreorder(TreeNode node) {

    if (node == null) {

        return;

    }

    System.out.print(node.value + " "); /* first print data of node */

    printPreorder(node.left);   /* then recur on left subtree */

    printPreorder(node.right);  /* now recur on right subtree */

}

void printPreorder() {

    printPreorder(root);

}   

这就是我卡住的地方：如何打印特定节点之后的节点，而不仅仅是整个树？我以为会是：

 public TreeNode findPreorder(int key) // find node with given key  

{                            // (assumes non-empty tree)  

    TreeNode current = root;                // start at root  

    while (current.value == key) // while there is a match  

    {

        current = current.left;

        if (key < current.value) // go left?  

        {

            current = current.right;

} 

我的输出是：

二叉树的前序遍历为 1 2 4 5 3

1之后的节点是5

有任何想法吗？谢谢！！

Answer 1

您基本上可以使用相同的功能以预购方式进行访问，并进行一些修改：void findNextInPreOrder(TreeNode node, int key) {&nbsp; &nbsp; if (node == null) {&nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; }&nbsp; &nbsp; if (node.value == key) {&nbsp; &nbsp; &nbsp; &nbsp;if(node.left != null){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print("Next is on left: " + node.left.value);&nbsp; &nbsp; &nbsp; &nbsp;} else if (node.right != null){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print("Next is on right: " + node.right.value);&nbsp; &nbsp; &nbsp; &nbsp;} else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print("There is no next node.");&nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; }&nbsp; &nbsp;&nbsp; &nbsp; findNextInPreOrder(node.left);&nbsp; &nbsp;/* then recur on left subtree */&nbsp; &nbsp; findNextInPreOrder(node.right);&nbsp; /* now recur on right subtree */}

Answer 2

我还添加了一个“else”语句，因为这似乎对我的实现有所帮助：void findNextInPreOrder(Node node, int key) {&nbsp; &nbsp; if (node == null) {&nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; }&nbsp; &nbsp; if (node.value == key) {&nbsp; &nbsp; &nbsp; &nbsp; if (node.left != null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print("Next is on left: " + node.left.value);&nbsp; &nbsp; &nbsp; &nbsp; } else if (node.right != null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print("Next is on right: " + node.right.value);&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print("There is no next node.");&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; findNextInPreOrder(node.left, key);&nbsp; &nbsp; &nbsp; &nbsp; /* then recur on left subtree */&nbsp; &nbsp; &nbsp; &nbsp; findNextInPreOrder(node.right, key);&nbsp; &nbsp; &nbsp; &nbsp; /* now recur on right subtree */&nbsp; &nbsp; }}