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

Question

我正在构建一个具有中序迭代器和预序迭代器的二叉搜索树 class。我已经为中序迭代器编写了一个尝试，但我认为我的代码不正确。我阅读了一些关于对迭代器进行编码的指南，并采用了我所解释的内容并尝试在我的设计中实现它。返回树的 hasNext 是有问题的。当前 tree.isEmpty() returns 树的根节点是否为空。我不确定在树的迭代过程中检查是否正确。

我对我对 Inorder 迭代如何工作的理解并不完全自信。目前，我从 root.left 开始使用 next() 方法，而不是尝试从那里进行迭代。

代码澄清的一些注释 E = 节点的元素/数据 K = 键

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

首先，检查构造函数。 Iterators 应该很快并且通常使用底层数据结构的 实时副本 。因此，我建议不要每次都创建一个新树。

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

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

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

现在，next() 方法。首先，如果当前迭代器没有更多元素，请确保抛出 NoSuchElementException 。我们现在将简单地使用 !hasNext()。然后你按照以下步骤操作：

将节点压入栈中，直到当前节点没有左child。
如果currentNode为null且Stack不为空，pop()一个节点，向右更新currentNodechild 和 return 包含的节点数据。下次调用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 传递给 Iterator。当然，您必须在树中实现该功能并在每次修改时递增数字。

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();
    // ...
}

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

Binary Search tree inorder iterator next method

java

iterator

binary-search-tree

inorder