如何使用递归生成器遍历二叉树？ [英] How to traverse a binary Tree with a recursive generator?

问题描述

我正在尝试遍历在以下代码中创建的二叉树。确切地说，二叉树是一个类，应该包含一个调用另一个函数的迭代器，即inorder（）。这个方法应该是一个递归生成器并在每次迭代中产生节点的值。我试图创建一个跟随节点的字典但是当我尝试调用inorder（）方法时，它不起作用。有什么遗漏点我不知道吗？我使用while而它创建了树左侧的字典（这是一种笨拙的方式）。
请帮我完成此代码。

I am trying to traverse a Binary Tree which is created in the following code. to be precise, the Binary Tree is a class and should include an iterator calling another function namely inorder(). this method should be a recursive generator and yield the value of nodes in every iteration.I tried to create a dictionary to follow the nodes but when I try to call the inorder() method, it doesn't work. Is there any missing point that I don't know? I used while and it creates the dictionary of left side of tree (it is a clumsy way). please help me accomplish this code.

d=[]

# A binary tree class.
class Tree(object):
    def __init__(self, label, left=None, right=None):
        self.label = label
        self.left = left
        self.right = right
        self.d=dict()
    def __repr__(self, level=0, indent="    "):
        s = level * indent + self.label
        if self.left:
            s = s + "\n" + self.left.__repr__(level + 1, indent)
        if self.right:
            s = s + "\n" + self.right.__repr__(level + 1, indent)
        return s

def traverse(self):
    if self.left:
        lastLabel=self.label
        self.left.traverse()
    if self.right:
        lastLabel=self.label
        d.append(lastLabel)
        self.right.traverse()
    else:
        d.append(self.label)
    return d

def __iter__(self):
    return inorder(self)

# Create a Tree from a list.
def tree(sequence):
    n = len(sequence)
    if n == 0:
        return []
    i = n / 2
    return Tree(sequence[i], tree(sequence[:i]), tree(sequence[i+1:]))

# A recursive generator that generates Tree labels in in-order.
def inorder(t):
    for i in range(len(d)):
        yield d[i]    

def test(sequence):
# Create a tree.
    t = tree(sequence)
# Print the nodes of the tree in in-order.
    result = []
    for x in t:
        result.append(x)
    print x
    print

    result_str = ''.join(result)

# Check result
    assert result_str == sequence
    del d[:]
def main():
    # Third test
    test("0123456789")

    print 'Success! All tests passed!'

if __name__ == '__main__':
    main()

我再次更改了代码
我完成了代码，但我确信它不是遍历二叉树的最佳方式。
我在我的类中定义了一个方法-traverse（） - 现在返回一个按顺序的节点列表（最初没有订购，所以我使用了sort（）方法。）然后我在我的生成器inorder（）函数中对这个列表进行了循环，以产生它的元素。
非常欢迎您的所有评论以优化代码。
请根据此代码中的特定Tree类推荐一个合适的解决方案。

I changed my code again I accomplished the code but I'm sure it is not the best way to traverse a Binary tree. I defined a method -traverse()- in my class and returned a list of nodes in order now (which at first wasn't ordered, so I used sort() method.) then I made a loop over this list in my generator, inorder() function, to yield the element of it. All your comments are very welcome to optimize the code. please recommend a proper solution based on the specific Tree class in this code.

推荐答案

也许我遗漏了一些东西，但我不确定为什么字典与 inorder（）相关。想想一般的有序遍历是什么样的：

Perhaps I'm missing something, but I'm not sure why the dictionary is relevant in inorder(). Think about what an in-order traversal looks like in general:

def inorder(t):
    # Process left sub tree
    # Process t
    # Process right sub tree

等等生成器的术语，如下所示：

and so in terms of generators, this would look like:

def inorder(t):
    if t.left:
        for elem in inorder(t.left):
            yield elem
    yield t
    if t.right:
        for elem in inorder(t.right):
            yield elem

这篇关于如何使用递归生成器遍历二叉树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！