二叉搜索树添加方法参考迷路

Question

我正在编写自定义二叉搜索树 class，但由于某种原因，分配给节点的值总是丢失。这是我的方法。

private void add(TreeNode node, int a) {
    if(node==null) {
        System.out.println("node=null");
        node = new TreeNode(a);

    }else {
        if(a<node.value) {
            System.out.println("root > value "+"root: "+node.value+"value: "+a);

            add(node.left, a);

        }else {

            System.out.println("root < value "+"root: "+node.value+"value: "+a);

            add(node.right, a);

        }
    }
}

//root is class data
public void add(int a) {
    add(root, a);
}

当我运行这样做时，控制台屏幕总是打印出 node=null，第一个 if 语句从不检查 false，这意味着值从未实际分配给我的节点。我认为参考资料丢失了某处，但我不知道在哪里。

Answer 1

我看到的问题：

如果需要，您没有在链接的代码中初始化根目录。您正在创建一个新节点，但如果需要，请不要设置根节点。（提示：第一次插入需要设置根！，可能需要在您的 public 方法中进行检查）
传递 node.left / node.right 时，您永远不会检查是否需要在必要时设置新的左/右子节点

例如

if(a < node.value){
    if(node.left == null){
        //set the new left node
        node.left = new TreeNode(a); //STOP CONDITION!
    }else{
        add(node.left, a);           //Recurse left down the BST!
    }
}

您正在使用递归，因此您需要有一个适当的停止条件。虽然您的代码确实在某个点停止，但它实际上并没有按照您的意愿进行。为了正确起见，您需要确保正在设置新的子节点引用（在上面的代码中提示）。当您向左递归时，您将沿着 BST 传播新值，直到您最终需要创建一个新的叶节点。当沿着树向下递归时，应该会发生类似的事情。

在您的情况下，您只会传递左/右节点值，直到达到 null，并且永远不会更新子节点引用。

二叉搜索树添加方法参考迷路

Binary Search Tree add method reference get lost

java

reference

binary-search-tree