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

您没有将元素分配给 left 或 right 子项。您只是将其分配给局部变量 currentNode - 未链接到树。

按照下面的代码放入 while 循环中，它应该适合你。

            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;
                }
            }

Answer 2

事实上，您在递归步骤中没有正确地将新节点添加到树中。您应该使用的逻辑是，当您到达一个节点，其左指针或右指针为 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;
        }
    }
}

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

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

Anomaly with linking objects in Java binary tree implementation

java

binary-tree

data-structures