1

我的枚举器中的 MoveNext 方法有问题。我需要二叉搜索树的迭代器。在我的枚举器的构造中，我将 Node 初始化为树的根。当前是我为下一项返回的值。此方法 moveNext 的代码返回错误值。

public bool MoveNext()
    {

        if (Current == null)
            Current = node.Value;
        else if (node.Left != null)
        {
            node = node.Left;
            Current = node.Value;
        }
        else if (node.Right != null)
        {
            node = node.Right;
            Current = node.Value;
        }
        else
        {
            node.Value = Current;
            do
            {
                if (node.Parent == null)
                    return false;
                node = node.Parent;
            } while (node.Right == null);
            Current = node.Value;
        }
        return true;

    }
4

4 回答 4

2

我看到该代码存在一些问题。首先，在else-branch 中，您正在更改树中节点的值 - 您可能打算写Current = node.Value;而不是node.Value = Current;.

然而，这不是主要问题。你的迭代器很容易陷入无限循环。一切看起来都是合理的向下遍历，你沿着最左边的路径向下到叶节点。

然后你回溯，直到找到一个有Right子节点的祖先节点并产生该节点的值。但是，迭代器在下降的过程中已经返回了这个值。而且，你不记得你已经走过了哪条路，所以在下一步，你将不可避免地再次沿着你之前走的同一条路向下走，然后你会再次原路返回，以此类推，无止境。

为了解决这个问题，当你回溯时不要停在父节点 - 已经迈出了下一条路径的第一步。确实，这将始终是Right某个节点的子节点，但不一定是第一个Right祖先的子节点，因为您可能已经从该分支回溯。

所以总结一下：如果你不能再往下走，就回溯上一层。检查您是否来自子节点Left或Right子节点。如果您来自左侧，如果存在，则从右侧向下走，并设置Current为它的值。如果不是，或者如果你已经来自正确的孩子，则向上递归另一个级别。

于 2013-10-27T11:19:11.943 回答
1

您的枚举器修改了树：

Node.Value = Current;

枚举器不应该这样做。

于 2013-10-27T11:04:51.920 回答
0

在最后一个 else 中，您将节点的值更改为与当前节点相同的值：

node.Value = Current;

我认为您试图将当前节点放入node变量中，但这不是通过将当前值放入当前节点的值中来完成的，因为node变量已经包含当前节点，所以不需要这样做。

正如 Medo42 指出的那样，如果您来自 Right 节点，则该父节点的所有子节点都已被迭代，因此在寻找父节点以继续迭代时应检查这一点：

} while (node.Right == null || node.Right == last);

当您循环父链以找到正确的父链时，您正在使用父链而不是获取子链：

node = node.Right;

所以：

public bool MoveNext() {

    if (Current == null)
        Current = node.Value;
    else if (node.Left != null)
    {
        node = node.Left;
        Current = node.Value;
    }
    else if (node.Right != null)
    {
        node = node.Right;
        Current = node.Value;
    }
    else
    {
        Node last;
        do
        {
            if (node.Parent == null)
                return false;
            last = node;
            node = node.Parent;
        } while (node.Right == null || node.Right == last);
        node = node.Right;
        Current = node.Value;
    }
    return true;

}
于 2013-10-27T11:06:27.217 回答
0

我在这里发布了我的解决方案 Binary Search Tree Iterator java

源代码 https://github.com/yan-khonski-it/bst/blob/master/bst-core/src/main/java/com/yk/training/bst/iterators/BSTIterator.java

这是算法如何做到这一点（你可以用你喜欢的任何语言来实现它）。

数组迭代器

BSTITerator 在底层使用数组。

执行中序遍历并将访问过的节点收集到一个列表中。数组迭代器。现在它的工作方式类似于列表迭代器，易于实现。

next()-hasNext()具有恒定的时间复杂度；但是，此迭代器需要存储树的 N 个元素的内存。

堆栈迭代器

调用中要返回的所有节点next()都存储在堆栈中。每次，你返回下一个节点，你从堆栈中删除元素（让我们命名它currentNode）。如果currentNode有一个右孩子（你已经返回了左边），你将右孩子放入堆栈。然后你需要迭代右孩子的左子树并将所有左元素放入堆栈。

于 2020-05-03T16:53:09.480 回答