如何基于二叉树迭代器创建字典的键、值可迭代对象？

这其实是个典型的迭代器包装/转换场景，既然受限于ADT不能修改二叉树类，那我们完全可以通过包装现有接口返回的迭代器来实现需求。下面分两种常用方式给出具体实现：

方案一：基于字典已有的entries()方法实现 #

既然entries()已经能正常返回Iterable<Entry<K, V>>，我们只需要创建一个新的Iterable，它的迭代器会遍历条目并提取对应的键或值。这种方式的好处是完全依赖字典的公开接口，不需要直接操作底层二叉树。

键的Iterable实现 #

public Iterable<K> keys() {
    // 返回一个自定义的Iterable，其迭代器包装entries的迭代器
    return () -> new Iterator<K>() {
        // 获取entries迭代器作为底层迭代器
        private final Iterator<Entry<K, V>> entryIterator = entries().iterator();

        @Override
        public boolean hasNext() {
            // 直接复用底层迭代器的hasNext判断
            return entryIterator.hasNext();
        }

        @Override
        public K next() {
            // 取出下一个Entry，返回它的key
            return entryIterator.next().key;
        }
    };
}

值的Iterable实现 #

逻辑和键的实现几乎一致，只是提取value：

public Iterable<V> values() {
    return () -> new Iterator<V>() {
        private final Iterator<Entry<K, V>> entryIterator = entries().iterator();

        @Override
        public boolean hasNext() {
            return entryIterator.hasNext();
        }

        @Override
        public V next() {
            return entryIterator.next().value;
        }
    };
}

如果你的项目使用Java 8及以上，还可以用更简洁的Lambda结合Stream来实现（本质和匿名内部类逻辑一致）：

public Iterable<K> keys() {
    return () -> entries().stream().map(entry -> entry.key).iterator();
}

public Iterable<V> values() {
    return () -> entries().stream().map(entry -> entry.value).iterator();
}

方案二：直接基于二叉树的getInorderIterator()实现 #

如果你的字典类持有底层二叉树的引用（比如private final BinaryTree<Entry<K, V>> tree;），也可以直接包装二叉树的中序迭代器来实现，逻辑和上面完全一致：

键的Iterable实现 #

public Iterable<K> keys() {
    return () -> new Iterator<K>() {
        private final Iterator<Entry<K, V>> treeIterator = tree.getInorderIterator();

        @Override
        public boolean hasNext() {
            return treeIterator.hasNext();
        }

        @Override
        public K next() {
            return treeIterator.next().key;
        }
    };
}

值的Iterable实现 #

public Iterable<V> values() {
    return () -> new Iterator<V>() {
        private final Iterator<Entry<K, V>> treeIterator = tree.getInorderIterator();

        @Override
        public boolean hasNext() {
            return treeIterator.hasNext();
        }

        @Override
        public V next() {
            return treeIterator.next().value;
        }
    };
}

核心思路说明 #

这种实现的核心是迭代器的适配器模式：我们不修改原有的迭代器逻辑，只是在它外面套一层“转换器”，把Entry类型的元素转换成我们需要的K或V类型。这样做完全符合ADT的封装原则——我们只依赖公开的接口方法，不需要访问二叉树的内部结构，也不需要修改二叉树类的代码。

另外要注意，这种包装后的迭代器和原迭代器是联动的：如果在遍历键/值的过程中修改了字典（比如添加或删除条目），迭代器的行为会和原entries()或getInorderIterator()的迭代器保持一致（遵循原迭代器的fail-fast或其他约定）。

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