java - InOrder 遍历进入无限循环并仅打印第一个节点

Question

我试图编写一段简单的代码来通过 inorder 遍历来遍历二叉搜索树。我能够完美地纠正插入代码，因为调试器显示的树与我想要的一模一样。但是我的递归遍历没有给出正确的结果。这是我的调试器的屏幕截图:

左子树后跟右子树

对应如下可视化树:

它不是打印出所有节点，而是无限循环地打印第一个元素 (39)。这是我的代码:主.java

public class Main {

public static void main(String[] args) {
   BinaryTree binaryTree = new BinaryTree();
    binaryTree.add(50);
    binaryTree.add(40);
    binaryTree.add(39);
    binaryTree.add(42);
    binaryTree.add(41);
    binaryTree.add(43);
    binaryTree.add(55);
    binaryTree.add(65);
    binaryTree.add(60);
    binaryTree.inOrderTraversal(binaryTree.root);
}
}

Node.java

public class Node {
int data;
Node left;
Node right;
Node parent;


public Node(int d)
 {
   data = d;
   left = null;
   right = null;
 }
}

二叉树.java

public class BinaryTree {
Node root = null;
public void add(int d)
{
    Node newNode =  new Node(d);
    if(root!=null)
    {


        Node futureParent = root;
        while(true)
        {
        if(newNode.data < futureParent.data)      //going left
        {
            if(futureParent.left == null)
            {
                futureParent.left = newNode;
                newNode.parent = futureParent;
                break;
            }
            futureParent = futureParent.left;

        }
        else
        {
            if(futureParent.right == null)
            {
                futureParent.right = newNode;
                newNode.parent = futureParent;
                break;
            }
            futureParent = futureParent.right;
        }

        }

    }
    else
    {
        root = newNode;
    }
}
public void inOrderTraversal(Node node)
{
    while(node!=null)
    {
    inOrderTraversal(node.left);
    System.out.println(node.data);
    inOrderTraversal(node.right);
    }
}
}

Answer 1

您不需要在 inOrderTraversal() 中使用 while() 循环。这是一个递归调用。它导致了无限循环。

但是，您确实需要一些东西来停止递归。仅当节点不为空时才递归。

public void inOrderTraversal(Node node) {
    if(node==null) return;

    inOrderTraversal(node.left);
    System.out.println(node.value);
    inOrderTraversal(node.right);
}