二叉搜索树迭代器 c#

本文关键字：迭代器 搜索树 | 更新日期: 2023-09-27 18:36:58

我的枚举器中的方法 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;
    }

二叉搜索树迭代器 c#

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

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

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

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

。

所以总结一下：如果你不能再往下走，那就往上回溯一个级别。检查您来自Left还是Right子节点。如果您来自左侧，请向下移动右侧（如果存在），并将Current设置为其值。如果没有，或者你已经来自正确的孩子，那就再往上爬一个层次。

枚举器修改树：

Node.Value = Current;

枚举器不应这样做。

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

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;
}

我在这里发布了我的解决方案二叉搜索树迭代器 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有一个右子项（您已经返回了左子项），则将右子项放入堆栈中。然后你需要迭代右子元素的左子树，并将所有左元素放入堆栈中。

相关文章：