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

hjqgdpho 于 2021-07-03 发布在 Java

关注(0)|答案(1)|浏览(316)

我正在构建一个二叉搜索树类，它有一个有序迭代器和一个预有序迭代器。我已经为顺序迭代器编写了一个尝试，但是我认为我没有正确的代码。我阅读了一些关于迭代器编码的指南，我接受了我解释的内容，并尝试在我的设计中实现它。下一个还树的人是可疑的。当前tree.isempty（）返回树的根节点是否为空。我不确定在树的迭代过程中检查是否正确。
我不完全相信我对有序迭代工作原理的理解。目前，我从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();
    }
}

Java Iterator binary-search-tree InOrder

来源：https://stackoverflow.com/questions/65186904/binary-search-tree-inorder-iterator-next-method

1条答案

按热度按时间

d7v8vwbk1#

首先，检查施工人员。 Iterators 应该是快速的，并且通常使用底层数据结构的实时副本。因此，我建议不要每次都创建新树。

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() 剩下的。这个方法现在也应该很清楚了，因为它可以通过反转 while 条件 next() .

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

赞(0）回复(0）举报 2021-07-03

我来回答

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

1条答案

相关问题

热门标签

最新问答