BinarySearchTree 插入方法

Question

我正在尝试使用递归为 BST 编写插入方法。

 public void insert(DictEntry data) throws BSTException {
     if (find(data.getPosition()) == data){
         throw new BSTException();
     }
     else {
         if (current == null){
             root.setRoot(data);
     }
         else {
             while(current != null){
                 if (data.getPosition().compareTo(root.getRoot().getPosition()) < 0){
                     current = current.getLeft();
                 }
                 else{
                     if (data.getPosition().compareTo(root.getRoot().getPosition()) > 0){
                         current = current.getRight();
                     }
                     else
                         ;
                 }
                 insert(data);
             }
         }

     }
 }

但我不知道为什么测试用例总是失败。有人可以帮我解决吗？

Answer 1

此代码存在一些问题：

您混淆了递归实现和迭代实现。通过在函数 "insert" 中调用 "insert(data)" 来使用递归时，您不需要 "while" 循环
当您最终达到递归的基本情况时 if (current == null){ 您会在根部插入吗？您应该在 "current" 插入，因为这是您发现为空的子树并匹配顺序
您总是将您的数据与 "root" 而不是 "current"

其他问题：

您的代码格式错误（第一个 "else" 之后的“}”应该缩进更多，"else ;" 是不必要的）
您正在通过更新函数外部的变量来使用递归："current"。这可能有效，但它是糟糕的风格。您的方法应该类似于 public void insert(DictEntry data, BSTNode node)，您从 insert(data, root) 开始，然后递归调用 insert(data, node.getLeft() 或 insert(data, node.getRight()

BinarySearchTree 插入方法

BinarySearchTree insert method

java

insert

binary-search-tree