二叉搜索树序迭代器next方法

Question

public class BSTIterator<E, K> implements StructureIterator<E> {

    private final BST<E, K> tree;
    BSTNode<E> root =null;
//    Comparator<E> sortFct;
//    BiFunction<K, E, Integer> searchFct;

    public BSTIterator( BSTNode<E> root,Comparator<E> sortFct,
                        BiFunction<K, E, Integer> searchFct) {
        this.tree = new BST<E, K>(sortFct, searchFct);
        this.root = root;
    }

    @Override
    public E next() {
        BSTNode<E> node = tree.root.getLeft();
        E result = node.getData();
        if(node.getRight() != null){
            while(node != null){
                tree.root.getRight();
                node = node.getLeft();
            }
        }
        return result;
    }

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

Answer 1

首先，考察构造函数。迭代器应该是快速的，并且通常使用底层数据结构的实时副本。因此，我建议不要每次都创建一个新树。

public BSTIterator(BST<E, K> tree) {
    this.currentNode = tree.getRoot();
}

现在，要在不使用递归的情况下遍历树结构，可以使用stack。同时，跟踪当前访问的节点。

Stack<BSTNode<E>> stack = new Stack<>();
BSTNode<E> currentNode;

现在，使用next()方法。若要开始，请确保在当前迭代器没有剩余元素的情况下抛出nosuchelementexception。我们现在只需使用！hasnext()。然后按照以下步骤操作：

• 将节点推送到堆栈中，直到当前节点没有左子节点。
• 如果CurrentNode为Null且Stack不为空，POP()为节点，则将CurrentNode更新为正确的子节点并返回包含的节点数据。下次调用next()时，遍历将在此位置继续。
• 如果CurrentNode为Null且堆栈为空，则完成操作。

这是next()的实现：

@Override
public E next() {
    if(!hasNext())
        throw new NoSuchElementException();

    while(!stack.empty() || currentNode != null) {
        if(currentNode != null) {
            stack.push(currentNode);
            currentNode = currentNode.getLeft();
        } else {
            BSTNode<E> node = stack.pop();
            currentNode = node.getRight();
        
            return node.getData();
        }
    }
}

从这里开始，只剩下hasNext()。这个方法现在也应该很清楚了，因为它可以通过反转next()中的while条件来实现。

@Override
public boolean hasNext() {
    return stack.empty() && currentNode == null;
}

高级功能：

大多数Java集合跟踪修改计数，或简称modcount。它存储一个集合被修改的次数。此数据可用于检测底层数据结构在迭代时何时被非法修改。只需将modcount传递给迭代器。当然，您必须在树中实现该特性，并在每次修改时增加该数字。

public BSTIterator(BST<E, K> tree) {
    this.tree = tree;
    this.currentNode = tree.getRoot();
    this.expectedModCount = tree.modCount;
}

然后,实现fail-fast行为：

@Override
public E next() {
    if(expectedModCount != tree.modCount)
        throw new ConcurrentModificationException();
    // ...
}