我执行 BST 插入有什么问题？ Java

Question

我想了解 BST 插入算法的工作原理。我正在递归执行此操作，但我对它为何无法正常工作感到有些困惑。

   public boolean insert(int key) {
        return insertHelper(root, key);
    }

    private boolean insertHelper(TreeNode sub, int key) {
        if (sub == null) {
            sub = new TreeNode(key);
            return true;
        } else if (sub.getData() > key) {
            return insertHelper(sub.getLeftChild(), key);
        } else
            return insertHelper(sub.getRightChild(), key);
    }

树节点构造函数

 public TreeNode(int data) {
    this.data = data;
}

问题是当我遍历树来打印元素时，树一直是空的。一定是插入算法有问题。

Answer 1

因为您没有在代码的任何部分设置任何左右 child。将 insertHelper 实现到 return TreeNode 而不是布尔值的最佳技术。此代码段可能会有所帮助。

    private Node<T> insert(Node<T> p, T toInsert){
      if (p == null)
         return new Node<T>(toInsert);

      if (compare(toInsert, p.data) == 0)
        return p;

      if (compare(toInsert, p.data) < 0)
         p.left = insert(p.left, toInsert);
      else
         p.right = insert(p.right, toInsert);
      return p;
   }

Answer 2

它仍然是空的，因为你的根总是 null。

在java中，所有参数均按值传递。所以这段代码：

// ....
    if (sub == null) {
        sub = new TreeNode(key);
        return true;
//....

将创建新节点，但不会更新根节点。

我执行 BST 插入有什么问题？ Java

What is wrong with my implementation of BST insert? Java

java

algorithm

binary-search-tree