节点之间具有链表的BST

Question

我正在尝试使用（不平衡的）BST实现树集。我还希望为树中的所有节点维护一个有序的双链接列表。

TreeSet<Integer> set = new TreeSet<>();
set.add(10);
set.add(5);
set.add(15);
set.add(12);
// The linked list would be 5 <-> 10 <-> 12 <-> 15

链表是在2个前哨节点的帮助下维护的，一个头节点和一个尾节点。因此，要遍历链表，您需要从头节点开始，检查它的. Next属性。

class Node<T extends Comparable<? super T>> {
    private Node<T> left, right,
                    prev, next;
}

我有一个递归的add方法，就像这样；

boolean add(T data) {
    int oldSize = getSize();
    root = add(data, root, head, tail);
    return getSize() != oldSize;
}


Node<T> add(T data, Node<T> n, Node<T> low, Node<T> high) {
    if (n == nullNode) {
        n = new Node<T>(data);
        n.left = n.right = nullNode;
        // But what do I do now to update the linked list?
    } else {
        int result = compare(data, n.data);
        if (result < 0) {
            n.left = add(data, n.left, low, n);
        } else if (result > 0) {
            n.right = add(data, n.right, n, high);
        }
    }

    return n;
}

其中low和high设置在链表中将插入新节点的位置的边界。

我在维护节点的Next和prev属性时遇到了问题。

Answer 1

您必须跟踪上一个节点。i、 e.以前访问过的节点。

这是通过查找无序前身来完成的。无序前驱是节点的左边子树的最右边的叶子。

同样，您必须找到设置下一个节点的顺序继承者。

当然，这里也有例外——如果节点是叶呢？在这种情况下，inorder PRESIONER将是第一个祖先，其右子树将包含当前节点。类似地，用于查找下一个节点。

在线查看inorder的前身和后续概念。

注意：这不是最有效的方法，但应该是一个很好的开始方法。