java - 自定义treeSet类，如何编写迭代器

Question

我正在尝试创建自己的二叉搜索树。但我想不出任何方法来实现具有 hasNext()、next() 的工作迭代器。我的想法是，遍历二叉搜索树的唯一方法是通过递归。但是，如果我尝试使用 next，如何才能保存递归调用，以便在再次调用 next 并返回值时恢复它呢？还有其他办法吗

import java.util.Iterator;

public class TreeWordSet implements WordSetInterface {
    private BST root = null;

    private class BST {
        Word value;
        BST left = null;
        BST right = null;

        BST(Word word) {
            value = word;
        }

        void add(Word newWord) {
            if (newWord.compareTo(value) < 0) {
                if(left == null) {
                    left = new BST(newWord);
                } else {
                    left.add(newWord);
                }
            } else if (newWord.compareTo(value) > 0) {
                if (right == null) {
                    right = new BST(newWord);
                } else {
                    right.add(newWord);
                }
            }
        }
    }

    @Override
    public void add(Word word) {
        if (root == null) {
            root = new BST(word);
        } else {
            root.add(word);
        }
    }

    @Override
    public boolean contains(Word word) {
        return false;
    }

    @Override
    public int size() {
        return 0;
    }

    private class TreeWordSetIterator implements Iterator<Word> {

        @Override
        public boolean hasNext() {
            return false;
        }

        @Override
        public Word next() {
            return null;
        }
    }

    @Override
    public Iterator<Word> iterator() {
        return new TreeWordSetIterator();
    }

}

Answer 1

如果这是一个以学习为目的的练习，也许最好的方法就是看看 TreeSet 是如何做到的。如果这是一个用于生产用途的练习，请立即停止，并在确实需要时扩展 TreeSet。