java - 如何在二叉树中找到下一个顺序后继者？

Question

我正在尝试在我自己的 TreeSet 类中实现一个迭代器。 但是，我创建它的尝试仅在当前节点成为根节点之前有效。 迭代器看起来像这样:

构造函数:

public TreeWordSetIterator()
{
    next = root;

    if(next == null)
        return;

    while(next.left != null)
        next = next.left;
}

有下一个:

public boolean hasNext()
{
    return next != null;
}

下一步:

public TreeNode next()
{
    if(!hasNext()) throw new NoSuchElementException();

    TreeNode current = next;

    next = findNext(next); // find next node

    return current;
}

查找下一个:

private TreeNode findNext(TreeNode node)
{
    if(node.right != null)
    {
        node = node.right;

        while(node.left != null)
            node = node.left;

        return node;
    }
    else
    {
        if(node.parent == null)
            return null;

        while(node.parent != null && node.parent.left != node)
            node = node.parent;

        return node;
    }
}

在我到达我的根节点之前，这一切都很好。所以我只能遍历root的左 child ，不能遍历右 child 。谁能给我一些关于我做错了什么的提示？我不期待解决方案，只是一些提示。

问题:如果每个节点都指向其父节点、左子节点和右子节点，我如何找到 TreeSet 中的下一个节点。

提前致谢

Answer 1

这有助于考虑 Binary Search Tree 的规则.假设之前返回的节点是n:

• 如果n有一个右子树，那么具有下一个值的节点将是右子树的最左边的节点。
• 如果 n 没有右子树，则具有下一个值的节点将是包含 n 的 n 的第一个祖先在它的左子树中。

您的代码可以正确处理第一种情况，但不能正确处理第二种情况。考虑 node 是树最左边的叶子的情况(起始情况)。 node 没有右 child ，所以我们直接转到 else。 node 有父节点，因此跳过 if 子句。 node.parent.left == node，所以 while 子句被跳过，根本没有执行。最终结果是 node 被返回。我希望您的迭代器永远继续返回同一个节点。