java - Java 二叉树实现中链接对象的异常

Question

我已经实现了一个简单的二叉树程序，但是在遍历树时遇到一个问题，只访问根元素。我怀疑节点没有链接。我尽力找出问题所在，但没有发现我的代码有任何问题。

我尝试在退出函数之前从插入函数打印数据，这确实正确打印了数据。

public class BinaryTree {

    Node root;

    public void addNode(int data){

        Node newNode = new Node(data);

        if(root == null){
            root = newNode;
        }
        else{
            Node currentNode = root;
            while(true){
                if(data <= currentNode.data){
                    currentNode = currentNode.leftChild;
                    if(currentNode == null){
                        currentNode = newNode;
                        return;
                    }
                } 
                else{
                    currentNode = currentNode.rightChild;
                    if(currentNode == null){
                        currentNode = newNode;
                        return;
                    }
                }
            }

        }
    }

    public void inorderTraversal(Node currentNode){

        if(currentNode != null){

            inorderTraversal(currentNode.leftChild);

            System.out.print(currentNode.data + " ");

            inorderTraversal(currentNode.rightChild);

        }
    }

}

Answer 1

事实上，您在递归步骤中没有将新节点正确添加到树中。您应该使用的逻辑是，当您到达左指针或右指针为 null 的节点时，并且新节点属于该方向，您应该添加新节点向左或向右。否则，继续遍历，直到到达该节点。

while(true) {
    if (data <= currentNode.data) {
        if (currentNode.leftChild == null) {
            currentNode.leftChild = newNode;
            return;
        }
        else {
            currentNode = currentNode.leftChild;
        }
    else {
        if (currentNode.rightChild == null) {
            currentNode.rightChild = newNode;
            return;
        }
        else {
            currentNode = currentNode.rightChild;
        }
    }
}

请记住，上述添加新节点的简单算法并不能保证一定会产生平衡二叉树。为了确保这一点，您必须添加更多处理重新平衡的逻辑。