通用二进制搜索树未正确添加新节点（Java）

Question

我正在用通用类在Java中编写一个二进制搜索树，但是节点未正确添加，所以我不知道为什么。

这是我的插入方法（迭代）：

public void insert (E element){
    //iterative insert element to tree

    Node<E> node = new Node<>(element); //create new node for element
    Node<E> current = root;

    if (root == null) root = node; // if no root, new node is the root

    else {
        while (current != null){ //traverse tree to get to correct parent node

            if (element.compareTo(current.data) < 0) { //case 1: node is smaller than current
                if (current.left == null){ 
                    node.parent = current;
                    current.left = node;
                }
                else {
                    current = current.left;
                }
            }
            else if (element.compareTo(current.data) > 0) { //case 2: node is larger than current
                if (current.right == null){
                    node.parent = current;
                    current.right = node;
                }
                else {
                    current = current.right;
                }
            }
            else { //case 3: node already exists
                throw new RuntimeException("Node already exists");
            }
        }
    }
    size++;
}

问题在我运行测试类时发生。在那里，第一个节点被添加并成为根节点，但是无论其值是多少，之后的下一个插入都会引发异常。它的行为就像我要添加的值已经存在于树中。如果我注释掉该异常，则测试类不会编译，就好像它正在运行一个无限循环。

我在这里做错了什么？

Answer 1

您的while循环中的电流怎么会变成空？

即使插入新元素，您也不会从while循环中跳出来：

if (current.left == null) { 
  node.parent = current;
  current.left = node;
}

在下一次迭代中，将电流分配给刚插入到current.left中的值：

} else {
  current = current.left;
}

并且在下一次迭代中，您现在具有与元素相等的current.data，这将导致异常。插入元素后添加break;：

if (current.left == null) { 
  node.parent = current;
  current.left = node;
  break;
}