java - 为 BST 支持的符号表创建 Iterable

Question

对于分配，我需要创建一个迭代，其中包含由二叉搜索树支持的符号表的所有键。我熟悉如何为链表执行此操作，但似乎无法在网上找到任何有关如何为 BST 执行此操作的示例。例如，对于链表，我会使用如下内容：

public Iterable<Key> keys() { 
    Queue<Key> queue = new Queue<Key>();
    for (Node x = first; x != null; x = x.next)
    queue.enqueue(x.key);
    return queue;
}

但我不太确定如何转换它，所以它保存了我 BST 的所有密钥。有人可以提供指导或链接到涵盖该主题的来源吗？

标签： javabinary-search-treesymbol-table

Answer 1

如果要先向左遍历，可以使用栈来实现。

static class Node<T> {
    T value;
    Node<T> left, right;
    
    Node(T value, Node<T> left, Node<T> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

和

static class BST<T> implements Iterable<T> {
    Node<T> root;
    
    public BST(Node<T> root) {
        this.root = root;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<>() {
            Deque<Node<T>> stack = new LinkedList<>();
            { pushAllLeft(root); }

            private void pushAllLeft(Node<T> node) {
                for ( ; node != null; node = node.left)
                    stack.push(node);
            }

            @Override
            public boolean hasNext() {
                return !stack.isEmpty();
            }

            @Override
            public T next() {
                Node<T> current = stack.pop();
                pushAllLeft(current.right);
                return current.value;
            }
        };
    }
}

和

public static void main(String[] args) {
    BST<Integer> bst = new BST<>(
        new BST.Node<>(3,
            new BST.Node<>(1,
                new BST.Node<>(0, null, null),
                new BST.Node<>(2, null, null)),
            new BST.Node<>(5,
                new BST.Node<>(4, null, null),
                new BST.Node<>(6, null, null))));

    for (int n : bst)
        System.out.println(n);
}

输出：

0
1
2
3
4
5
6