Java BST插入代码修正：根节点未填充致中序遍历异常

你的代码核心问题出在add方法的节点创建逻辑上，导致根节点始终无法被正确初始化，进而整个BST都没构建起来。让我一步步帮你修正：

问题根源 #

看你的私有add方法：

private Node add(Node node, int value) {
    if(node == null) {
        return node; // 这里错了！返回的是null，而不是新节点
    }
    // ... 其他逻辑
}

当第一次调用addNode(20)时，root是null，进入add(null, 20)，此时你直接返回了null，而不是创建一个包含20的新节点。这就导致root一直保持null，后续所有的插入操作都无效，最终输出"root is empty"。

修复步骤 #

1. 修正节点创建逻辑：把if(node == null)分支的返回值改成new Node(value)，这样遇到空位置时会创建新节点并返回，从而正确构建树。
2. 优化中序遍历的空节点提示：原代码中递归到空节点就会打印"root is empty"，这会导致输出里出现多次这句话。应该把空树的判断放在公开的inorder方法里，只在root本身为null时才提示。

修正后的完整代码 #

import java.util.*;
import java.io.*;
import java.lang.*;

class Node{
    int data;
    Node left;
    Node right;
    public Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

public class insert_tree {
    static Node root;
    
    insert_tree() {
        root = null;
    }
    
    public void addNode(int value) {
        root = add(root, value);
    }
    
    private Node add(Node node, int value) {
        if(node == null) {
            // 这里改为创建新节点返回
            return new Node(value);
        }
        if(value < node.data) {
            node.left = add(node.left, value);
        } else if(value > node.data) {
            node.right = add(node.right, value);
        } else {
            // 重复值不插入，直接返回原节点
            return node;
        }
        return node;
    }
    
    private void inOrder(Node node) {
        if(node != null) {
            inOrder(node.left);
            System.out.print(node.data + " ");
            inOrder(node.right);
        }
        // 移除空节点的打印逻辑
    }
    
    public void inorder() {
        if(root == null) {
            System.out.print("root is empty");
        } else {
            inOrder(root);
        }
    }
    
    private void printRoot(Node root) {
        if(root != null) {
            System.out.println(root.data);
        } else {
            System.out.println("root is empty");
        }
    }
    
    public void print() {
        printRoot(root);
    }
    
    public static void main(String args[]) {
        insert_tree obj = new insert_tree();
        obj.addNode(20);
        obj.addNode(14);
        obj.addNode(25);
        obj.addNode(10);
        obj.addNode(16);
        obj.addNode(25); // 重复值，不会被插入
        obj.addNode(21);
        obj.addNode(30);
        // 打印树的中序遍历
        obj.inorder();
    }
}

运行结果 #

修正后运行代码，会输出预期的中序遍历结果：

10 14 16 20 21 25 30 

内容的提问来源于stack exchange，提问作者swapnil