BST，节点之间有链表-Java 学习之路

我正在尝试使用（不 balancer ）BST实现TreeSet . 我还想为树中的所有节点维护一个有序的双向链表 .

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 属性时遇到问题 .

1 回答

0

您必须跟踪上一个节点 . 即先前访问过的节点 .

这是通过找到有序的前任来完成的 . Inorder的前身是节点左子树的最右边的叶子 .

以同样的方式，您必须找到用于设置下一个节点的inorder后继 .

当然，这里也有例外 - 如果节点是叶子怎么办？在这种情况下，incesscessor将是第一个祖先，其右子树将包含当前节点 . 同样，用于查找下一个节点 .

在线查看前身和后继概念 .

Note ：这不是最有效的方法，但应该是一个很好的入门方法 .

回复于 2024-04-27T19:18:43+08:00

BST，节点之间有链表

1 回答

相关问题