java - 二叉搜索树的迭代器不沿着树向下

Question

我一直在努力使用 Iterator 方法实现二叉搜索树。我一直在维基百科上查看这个算法:

def search_recursively(key, node):
    if node is None or node.key == key:
        return node
    if key < node.key:
        return search_recursively(key, node.left)
    # key > node.key
    return search_recursively(key, node.right)

我把它翻译成了 Java:

public Iterator<T> iterator()
    {
        return new Iterator<T>()
        {
            private int count = 0;

            @Override
            public boolean hasNext()
            {
                return count++ < size;
            }

            @Override
            public T next()
            {
                return search(root, root.word);
            }

            public T search(BST root, T word)
            {
                if (root == null || root.word.compareTo(word) == 0)
                {
                    return root.word;
                }

                if (root.word.compareTo(word) < 0)
                {
                    return search(root.left, word);
                }

                return search(root.right, word);
            }
        };

尝试运行程序时，我只得到 BST 的根元素:

MyWordSet bst = new MyWordSet();

T bst = new T("one");
T bst = new T("two");
T bst = new T("three");
T bst = new T("four");
T bst = new T("five");
T bst = new T("six");

bst.add(w1);
bst.add(w2);
bst.add(w3);
bst.add(w4);
bst.add(w5);
bst.add(w6);

Iterator<T> it = bst.iterator();

while (it.hasNext())
{
    System.out.println(it.next());
}

所以输出是:

one
one
one
one
one
one

那么为什么我的迭代器中的这个方法对我来说无法到达整棵树？我真的不知道这里出了什么问题，为什么它只在应该从树上掉下来的时候打印出一个。

Answer 1

您只是不更新​​current_node。

缺少 current_node = node 的等价物。

---

好了，改完代码后，这里修改一下答案:

import java.util.Iterator;
import java.util.Stack;

/**
 *
 * @author jk
 */
public class BSTIterator<T> implements Iterator<T> {

    public static final class BST<T> {

        private BST<T> left;
        private BST<T> right;
        private T word;

        private BST(T word) {
            this.word = word;

        }

    }
    private final Stack<BST<T>> stackBST = new Stack<>();

    public BSTIterator(final BST<T> root) {
        // push all most left entries of the tree to the stack
        BST<T> currBST = root;
        while (currBST != null) {
            stackBST.push(currBST);
            currBST = currBST.left;
        }
    }

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

    @Override
    public T next() {
        BST<T> currBST = stackBST.pop();

        // check if we are on the most right entry
        final boolean notMostRightEntry = currBST.right != null;
        if (notMostRightEntry) {
            // take next right entry 
            BST<T> nextBST = currBST.right;
            while (nextBST != null) {
                // push this next right entry on the stack
                stackBST.push(nextBST);
                nextBST = nextBST.left;
            }
        }
        return currBST.word;
    }

    public static void main(String[] args) {
        BST<Integer> root = new BST<>(20);
        root.left = new BST<>(5);
        root.right = new BST<>(30);
        root.left.right = new BST<>(10);
        root.right.left = new BST<>(25);
        root.right.right = new BST<>(40);
        root.right.left = new BST<>(35);
        root.right.left.left = new BST<>(32);
        for (Iterator<Integer> bstIt = new BSTIterator<>(root); bstIt.hasNext();) {
            System.out.println("val: " + bstIt.next());

        }
    }

}