使用递归时，二进制搜索树遍历无法执行

Question

我是 Java 编程和数据结构的新手。尽管如此，经过如此多的努力，我还是可以实现以下代码。这里我需要向节点插入值，并打印每个节点中的值，以在递归的帮助下演示所有 03 种类型的深度优先遍历技术。

PreOrder遍历
后序遍历
中序遍历

我开发了03个单独的方法来实现上面的03个遍历方法。（我已经评论了问题末尾给出的代码中的特定部分）

但是当我尝试运行代码时，我收到以下错误消息 Click here to view 作为参考，我以如下文本格式提供了错误消息。

Exception in thread "main" java.lang.NullPointerException
data -> 14
data -> 5
null
    at BSTreeDemo.BSTree.preOrderTraversal(BSTreeDemo.java:75)
    at BSTreeDemo.BSTree.preOrderTraversal(BSTreeDemo.java:75)
    at BSTreeDemo.BSTree.preOrderTraversal(BSTreeDemo.java:75)
    at BSTreeDemo.BSTree.preOrderTraversal(BSTreeDemo.java:75)
    at BSTreeDemo.BSTreeDemo.main(BSTreeDemo.java:16)

我不明白为什么会出现上述错误。因为在我看来我的做法是正确的。

以下是我实现的完整代码

package BSTreeDemo;

public class BSTreeDemo {

    public static void main(String[] args) {    //Main class
        BSTree t1 = new BSTree();
        t1.addNode(25);
        t1.addNode(14);
        t1.addNode(78);
        t1.addNode(45);
        t1.addNode(5);
        t1.addNode(89);
        
        System.out.println("-------------PreOrderTraversal------------");
        t1.preOrderTraversal(t1.root); 
        System.out.println("-------------PostOrderTraversal------------");
        t1.postOrderTraversal(t1.root); 
        System.out.println("-------------InOrderTraversal------------");
        t1.inOrderTraversal(t1.root); 
        
    }
    
}

class BSTNode {         // Binary Search tree node class
    int data; 
    BSTNode leftChild; 
    BSTNode rightChild; 
    
    public BSTNode(int data){ 
        this.data=data; 
    } 
    @Override 
    public String toString(){ 
        return "data -> "+data; 
    } 
}

class BSTree {
    
    BSTNode root; 
    
    public void addNode(int data) {     // method to add values to each node in binary search tree
        
        BSTNode newNode = new BSTNode(data);
        
        if(root == null){
            root=newNode;
        }
        else{
            BSTNode currentNode = root;
            while(true){
                BSTNode parentNode = currentNode;
                if(newNode.data<currentNode.data){
                    currentNode=currentNode.leftChild;
                    if(currentNode==null){
                        parentNode.leftChild = newNode;
                        return;
                    }
                }
                else{
                    currentNode = currentNode.rightChild;
                    if(currentNode ==null){
                        parentNode.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    } 
    
    public void preOrderTraversal(BSTNode currentNode){ // Recursive function to print the values in Pre-Order traversal
        System.out.println(currentNode);
        preOrderTraversal(currentNode.leftChild);
        preOrderTraversal(currentNode.rightChild);
        
        
    }
    
    public void postOrderTraversal(BSTNode currentNode){ // Recursive function to print the values in Post-Order traversal
        postOrderTraversal(currentNode.leftChild);
        postOrderTraversal(currentNode.rightChild);
        System.out.println(currentNode);  
    }
    
    public void inOrderTraversal(BSTNode currentNode){   // Recursive function to print the values in In-Order traversal
        inOrderTraversal(currentNode.leftChild);
        System.out.println(currentNode);       
        inOrderTraversal(currentNode.rightChild); 
    }
}

有人可以看一下我的代码吗，请指出我犯的任何愚蠢的错误，因为我没有成功运行代码，以及上面提到的原因错误？我现在真的很糟糕。

提前致谢。

Answer 1

您缺少递归遍历函数的基本条件，即 if (currentNode == null) return;

示例：

public void postOrderTraversal(BSTNode currentNode){ // Recursive function to print the values in Post-Order traversal
    if (currentNode == null)
        return;

    postOrderTraversal(currentNode.leftChild);
    postOrderTraversal(currentNode.rightChild);
    System.out.println(currentNode);
}

使用递归时，二进制搜索树遍历无法执行

Binary Search Tree Traversals failed to execute when using recursion

java

recursion

binary-search-tree