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 treepublic 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 31之后的节点是5有任何想法吗？谢谢！！

Answer 1

您基本上可以使用相同的功能以预购方式进行访问，并进行一些修改：

void findNextInPreOrder(TreeNode node, int key) {

    if (node == null) {

        return;

    }

    if (node.value == key) {

       if(node.left != null){

          System.out.print("Next is on left: " + node.left.value);

       } else if (node.right != null){

          System.out.print("Next is on right: " + node.right.value);

       } else {

          System.out.print("There is no next node.");

       }

    }   

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

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

}

Answer 2

我还添加了一个“else”语句，因为这似乎对我的实现有所帮助：

void findNextInPreOrder(Node node, int key) {

    if (node == null) {

        return;

    }

    if (node.value == key) {

        if (node.left != null) {

            System.out.print("Next is on left: " + node.left.value);

        } else if (node.right != null) {

            System.out.print("Next is on right: " + node.right.value);

        } else {

            System.out.print("There is no next node.");

        }

    } else {

        findNextInPreOrder(node.left, key);

        /* then recur on left subtree */

        findNextInPreOrder(node.right, key);

        /* now recur on right subtree */

    }

}