BSTD 中序遍历产生错误行为

Question

我有一个 BSTD 实现，它插入的值不正确，我终究无法找到发生了什么。

  EXPECTED ACTUAL  
  -------- ---------- 
  Alex     Janice    
  Carlos   Janice    
  Elton    Janice    
  Janice   Zidane    
  Zidane   Zidane

实施

private Node<K,E> insert(Node<K,E> node, K key, E elem) {

    if (node == null) {
        return new Node<K,E>(null, key, elem, null);
    }

    if (key.compareTo(node.getKey()) < 0) {
        return new Node<K, E>(insert(node.getLeft(), key, elem), key, elem, node.getRight());
    }
    else if (node.getKey().equals(key)) {
        return node;
    }
    else {
        return new Node<K, E>(node.getLeft(), key, elem, insert(node.getRight(), key, elem));
    }
}

我已经尝试调试了一个多小时但没有成功，知道我的递归哪里出错了吗？

Answer 1

是新节点，一般应该从节点中获取内容。

一定是equals/compare。更可靠的代码是：

int comparison = key.compareTo(node.getKey());
if (comparison < 0) {
    return new Node<K, E>(
        insert(node.getLeft(), key, elem),
        node.getKey(), node.getElem(),
        node.getRight());
}
else if (comparison == 0) {
    return node;
}
else {
    return new Node<K, E>(
        node.getLeft(),
        node.getKey(), node.getElem(),
        insert(node.getRight(), key, elem));
}

这仅依赖于 compareTo。

BSTD 中序遍历产生错误行为

BSTD inorder traversal produces erroneous behaviour

java

debugging

recursion

immutability