1

我上一堂cs课几乎没有吱吱作响，现在我在数据结构中。我正在从头开始构建一个二叉树结构，我对迭代器的工作方式有点困惑。我了解它们在双链表中的工作方式，但不确定这个将如何工作。

4

6 回答 6

1

所有其他答案都是关于如何在树结构上实现迭代器的技术讨论。但是，据我了解您的问题，您似乎无法理解树遍历概念的机制，而不仅仅是实现。换句话说，您不会“了解”树遍历。最有帮助的可能是获得一个好的伪代码算法来遍历二叉树、铅笔、一张纸，并计算出一个例子。构建一个简单的二叉树，然后自己机械地按照伪代码遍历它。您可能应该使用第二张纸来写出堆栈。也就是说，每个函数的状态，因为它正在等待子函数返回而被调用。

请记住，当你这样做时，一棵树是一个非常优雅的结构。它看起来很复杂，但在每个节点上都很简单。要对树中的所有元素执行操作，您只需在树的根部执行该操作，然后让该操作在该根的每个子节点上调用自身，这些子节点本身就是子树的根。自己设计一个例子将大大有助于让你的大脑理解和接受递归。如果您觉得很难，请不要感到困惑。递归很奇怪。一开始这是一个很难的概念，但有必要理解和使用树。

这是您可以用来启动的示例（ASCII 艺术）树：

      F
    / \
   / \
   DH
 / \ / \
 贝吉
/ \
交流电

还有一个简单的伪代码算法，您可以使用它以正确的顺序遍历编写所有字母。

过程遍历（节点）
    如果节点不为空：
        遍历（node.left）
        写节点.信
        遍历（node.right）
    别的：
        没做什么

您甚至可以从更简单的树开始。如果树只包含节点 D、F 和 H 怎么办？如果只有F呢？空值？尝试这些简单的示例，然后逐步构建更大的树。当您弄清楚如何始终如一且正确地执行此操作时，您不仅会对迭代器实现中发生的事情有一个非常好的感觉，而且您将对递归的力量有更好的理解。

于 2009-05-06T03:07:37.780 回答
0

“迭代器”是什么意思？如果您只需要迭代树，您可以递归地执行此操作： http ://en.wikipedia.org/wiki/Tree_traversal#Sample_implementations

如果您必须在 C# 或 Java 中提供 IEnumerator 接口，或者想要节省堆栈空间，请使用： http ://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal 您可以在 C# 中使用 yield 或轻松转换while 循环进入迭代器所需的“GetNext”方法。

于 2009-05-06T00:34:28.320 回答
0

我可以递归地做到这一点。我只是想在脑海中想象你是如何从一片叶子移动到另一片叶子的，因为从根开始有两种选择下一步去哪里，然后它只会增加 2^n 倍。这种工作方式的顺序让我感到困惑。

于 2009-05-06T00:47:33.123 回答
0

有两种主要的迭代树的方法。我在Iterative tree walk发布了一些示例 Python 代码，说明如何做到这一点。

于 2009-05-06T01:03:35.237 回答
0

在二叉树中，每个节点都会存储一些值并有 2 个子节点，例如左节点和右节点。现在遍历树的一种方法是从顶部开始，遍历左孩子，查看该节点的值，然后遍历右孩子。

遍历子节点意味着（递归）：1）遍历左子节点 2）查看节点的值 3）遍历右子节点

这是深度优先遍历，因此对于每个节点，您首先“使用”或“查看”它的左子节点的值，然后是当前节点的值，最后是右子节点的值。

对于广度优先遍历，您将从根开始，查看节点的值，然后将其子节点（如果存在）推送到队列中。然后在队列中有一个节点时循环，从队列的前面获取节点并重复：查看它的值，如果它有子节点，则将它们推到队列的末尾。

python中的示例：

#!/usr/bin/env python

    class Node:
        def __init__(self, val = 0):
            self.value = val
            self.left = None
            self.right = None

        def __str__(self):
            return "%d" % (self.value)

    def dfs(node = None):
        if node is None: return

        dfs(node.left)
        print node
        dfs(node.right)

    def bfs(root = None):
        if root is None: return

        nodes = []
        nodes.append(root)

        while len(nodes):
            current = nodes[0]
            print current
            nodes.remove(current)

        if current.left is not None:
            nodes.append(current.left)
        if current.right is not None:
            nodes.append(current.right)

    def main():
        root = Node(0)
        root.left = Node(10)
        root.right = Node(20)

        l = root.left
        l.left = Node(100)
        l.right = Node(101)

        r = root.right
        r.left = Node(200)
        r.right = Node(201)

        dfs(root)
        bfs(root)


    if __name__ == '__main__':
        main()



# example tree constructed:
#            0
#      10        20
#  100   101  200  201

# dfs (depth first) traversal:
# 100
# 10
# 101
# 0
# 200
# 20
# 201

# bfs (breadth first) traversal:
# 0
# 10
# 20
# 100
# 101
# 200
# 201
于 2009-05-06T01:24:29.807 回答
0

我在我的数据结构类中遇到了同样的问题。

我的解决方案相当简单。

递归遍历树，但将您访问的每个节点存储在另一个集合中，然后迭代该新集合。这样，编写迭代器就没有什么棘手的了。

我个人选择使用堆栈，但你可以用一个简单的数组，甚至是一个链表（你说你已经有经验）来做到这一点。

于 2009-05-06T01:41:23.993 回答