如何为基于BST的符号表实现返回所有键的Iterable方法

链表是线性结构，可通过单指针依次遍历所有节点，BST 为分层树结构，需要通过树遍历算法完成所有节点的枚举，行业常规采用中序遍历实现，保证返回的键按升序排列，符合 BST 符号表的设计预期。

递归实现（代码最简洁） #

递归实现逻辑清晰，是绝大多数场景下的首选方案：

public Iterable<Key> keys() { 
    Queue<Key> queue = new Queue<Key>();
    // 调用中序遍历辅助方法，从根节点开始遍历所有节点
    inorder(root, queue);
    return queue;
}

// 中序遍历私有辅助方法
private void inorder(Node x, Queue<Key> queue) {
    if (x == null) return;
    inorder(x.left, queue); // 先遍历所有左子树节点
    queue.enqueue(x.key); // 加入当前节点的键
    inorder(x.right, queue); // 再遍历所有右子树节点
}

该实现和你之前的链表版本keys()对外使用方式完全一致，返回的队列可直接迭代。

非递归实现（避免栈溢出） #

如果你的BST节点规模极大，递归深度过深可能触发栈溢出，可以用栈模拟中序遍历过程，实现非递归版本：

public Iterable<Key> keys() { 
    Queue<Key> queue = new Queue<Key>();
    Stack<Node> stack = new Stack<Node>();
    Node current = root;

    while (current != null || !stack.isEmpty()) {
        // 遍历到当前分支的最左节点
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        queue.enqueue(current.key);
        // 处理当前节点的右子树
        current = current.right;
    }
    return queue;
}

注意事项 #

• 如果你不需要返回升序排列的键，也可以替换为前序、层序等其他遍历方式，中序只是BST符号表的常规实现方案
• 代码中用到的Queue和你链表实现里的队列类完全兼容，不需要额外调整依赖

内容的提问来源于stack exchange，提问作者Justin123