java - 三元搜索树的顺序遍历

Question

所以，我有以下代码在三叉搜索树中插入一个元素(左树较少，中间相同，右树较大)

public void insert (TrinaryTree<T> root, T data) {
    //if the given tree doesn't exist yet
    if (root == null){
        root = new TrinaryTree<T>(data);
    }
    //if the given value is greater, insert to the right
    else if (root.getData().compareTo(data) > 0){
        insert (root.right, data);
    }
    //if the given value is equal, insert to the mid
    else if (root.getData().compareTo(data) == 0) {
        insert (root.mid, data);
    }
    //if the given value is less, insert to the left
    else {
        insert (root.left, data);
    }
}

然后我尝试打印出我的树(以便遍历检查我所做的是否正确或不使用它 -

public void inorderTraversal (TrinaryTree<T> root){
    if (root != null){
        inorderTraversal(root.getLeft());
        System.out.println(root.getData());
        inorderTraversal(root.getRight());      
    }
}

现在，当我尝试运行主类时，就是这个 -

public static void main (String [] args) {
    TrinaryTree<Integer> tree = new TrinaryTree<Integer>(5);
    tree.insert(tree, 4);
    tree.insert(tree, 9);
    tree.insert(tree, 5);
    tree.insert(tree, 7);
    tree.insert(tree, 2);
    tree.insert(tree, 2);       
    tree.inorderTraversal(tree);
}

我刚得到输出5。我想通了，因为主树的左右子树都为null。我不确定为什么会这样。我的插入函数有效，因为我将打印语句放入插入函数中，并且该语句确实被打印出来了。为什么子树仍然为空？

Answer 1

看insert的代码!一旦你用一个 null 值调用它(你想在左边或右边放一些东西)，那么很可能一切都是空的。

• root.left 和 root.right(可能)为空，您的代码不会将新创建的节点添加到上一级节点。
• 您调用 compareTo 的值可能为 null(没有 NPE？)

最重要的是，当您使用未初始化的值(左或右)调用insert 时，您的代码将创建一个TrinaryTree 节点，但它不会能够将它添加到它的父节点(您可能打算这样做)，并且新创建的节点将在方法调用后被垃圾收集。