在二叉搜索树上实现迭代器

Question

最近我一直在编码了一堆不同的二叉搜索树实现(AVL,扇,树堆),并很好奇,如果有一个特别"好"的方式来写一个迭代器遍历这些结构.我现在使用的解决方案是让BST中的每个节点都存储指向树中下一个和前一个元素的指针,这会将迭代减少到标准的链表迭代.但是,我对这个答案并不满意.它通过两个指针(下一个和前一个)增加每个节点的空间使用量,在某种意义上它只是作弊.

我知道的构建,通过使用堆栈跟踪前沿节点的探索以后用0-1(H)的辅助存储空间(其中,h为树的高度),二叉搜索树迭代器的方式,但我由于内存的使用,我们拒绝对此进行编码.我希望有一些方法来构建一个只使用常量空间的迭代器.

我的问题是 - 有没有办法在具有以下属性的二叉搜索树上设计迭代器？

1. 按升序访问元素(即按顺序遍历)
2. next()和hasNext()查询在O(1)时间内运行.
3. 内存使用量为O(1)

为了更方便,它的罚款,如果你认为迭代(即没有插入,删除或旋转)在树形结构不改变形状,但如果有,确实可以处理这样的解决方案将是真的很酷.

Answer 1

最简单的迭代器存储最后看到的键,然后在下一次迭代中,在树中搜索该键的最小上限.迭代次数为O(log n).这具有非常简单的优点.如果键很小,那么迭代器也很小.当然,它的缺点是迭代树的速度相对较慢.它也不适用于非唯一序列.

有些树完全使用您已经使用的实现,因为对于它们的特定用途而言,扫描速度非常快.如果每个节点中的密钥数量很大,则存储兄弟指针的代价并不太严重.大多数B树使用这种方法.

许多搜索树实现在每个节点上保留父指针以简化其他操作.如果你有,那么你可以使用指向最后一个节点的简单指针作为迭代器的状态.在每次迭代中,您将查找最后一个节点的父节点中的下一个子节点.如果没有兄弟姐妹,那么你再上一级.

如果这些技术都不适合您,则可以使用存储在迭代器中的一堆节点.当正常迭代搜索树时,它提供与函数调用堆栈相同的功能,但不是循环遍历兄弟节点并在子节点上递归,而是将子节点推送到堆栈并返回每个连续的兄弟节点.

Answer 2

正如TokenMacGuy所提到的,你可以使用存储在迭代器中的堆栈.以下是Java中快速测试的实现:

/**
 * An iterator that iterates through a tree using in-order tree traversal
 * allowing a sorted sequence.
 *
 */
public class Iterator {

    private Stack<Node> stack = new Stack<>();
    private Node current;

    private Iterator(Node argRoot) {
        current = argRoot;
    }

    public Node next() {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        Node node = current;
        current = current.right;

        return node;
    }

    public boolean hasNext() {
        return (!stack.isEmpty() || current != null);
    }

    public static Iterator iterator(Node root) {
        return new Iterator(root);
    }
}

其他变体是在构造时遍历树并将遍历保存到列表中.之后您可以使用列表迭代器.