Java BST中序遍历代码为何输出含多余*？问题出在哪？

兄弟，咱们直接揪出问题根源：你写的inOrder(Node node)方法里，那个else分支完全是多余的！

中序遍历的核心逻辑是只对非空节点执行「左子树→当前节点→右子树」的访问操作。当递归到node == null的时候，这说明已经到了叶子节点的尽头，根本不需要输出任何内容——但你现在在else里打印了*，导致每个有效节点的左右空指针都会触发一次这个输出，最后就出现了一堆多余的*。

修正后的代码 #

只需要把inOrder方法里的else分支删掉就行，修改后的完整代码如下：

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 { 
    Node root; 

    public void addNode(int value) { 
        root = add(root, value); 
    } 

    private Node add(Node node, int value) { 
        if(node == null) { 
            node = new Node(value); 
            return node; 
        } 
        if(value == node.data) { 
            node.left = add(node.left, value); 
        } else if(value < node.data) { 
            node.left = add(node.left, value); 
        } else { 
            node.right = add(node.right, value); 
        } 
        return node; 
    } 

    private void inOrder(Node node) { 
        if(node != null) { 
            inOrder(node.left); 
            System.out.print(node.data + " "); 
            inOrder(node.right); 
        } 
        // 删掉原来的else分支，null节点不需要输出
    } 

    public void inorder() { 
        inOrder(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); 
        //printing the tree 
        obj.inorder(); 
    } 
}

验证效果 #

运行修正后的代码，输出就是你预期的结果：

10 14 16 20 21 25 25 30

另外提一句，你插入重复值（比如两个25）的逻辑是放到左子树，这没问题，但如果有需要，也可以根据需求调整到右子树，不过这和当前的遍历问题无关啦。

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