首页 文章

如何使用递归生成器遍历二叉树?

提问于
浏览 93
3

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

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()

I changed my code again 我完成了代码,但我确信它不是遍历二叉树的最佳方法 . 我在我的类中定义了一个方法-traverse() - 并返回了一个节点 in order 的列表(起初它没有被排序,所以我使用了sort()方法 . )然后我在我的生成器中对这个列表进行了循环, inorder()函数,以产生它的元素 . 我们非常欢迎您的所有评论来优化代码 . 请根据此代码中的特定Tree类推荐合适的解决方案 .

2 回答

  • 5

    我对你的想法感到很困惑 . 首先,有一个理解为什么你介绍了 d 全局 .

    对于二叉树的有序遍历,您需要做的就是遍历左侧,当前标签和右侧:

    def inorder(tree):
        for label in tree.left:
            yield label
        yield tree.label
        for label in tree.right:
            yield label
    

    而已 .

    但是,我会对您的代码进行一些改进:

    # Document classes and functions with docstrings instead of comments
    class Tree(object):
        """A binary tree class"""
        def __init__(self, label, left=None, right=None):
            """Label is the node value, left and right are Tree objects or None"""
            self.label = label
            self.left = left   # Tree() or None
            self.right = right # Tree() or None
    
        def __repr__(self):
            return 'Tree(%r, %r, %r)' % (self.label, self.left, self.right)
    
        def __iter__(self):
            # No need for a separate inorder() function
            if self.left is not None:
                for t in self.left:
                    yield t
            yield self.label
            if self.right is not None:
                for t in self.right:
                    yield t
    
    def tree(indexable):
        """Return a tree of anything sliceable"""
        ilen = len(indexable)
        if not ilen:
            # You should be clearer about empty values
            # left and right should be Tree (something with left, right, and __iter__)
            # or None if there is no edge.
            return None 
        center = ilen // 2 # floor division
        return Tree(indexable[center], tree(indexable[:center]), tree(indexable[center+1:]))
    
    
    def test():
        seq = range(10)
        t = tree(seq)
        # list(t) will consume an iterable
        # no need for "result = []; for x in t: result.append(x)"
        assert seq == list(t)
    
    
    if __name__ == '__main__':
        test()
    
  • 1

    也许我'm missing something, but I'我不确定为什么字典在 inorder() 中是相关的 . 想一想有序遍历在一般情况下是什么样的:

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

    所以就发电机而言,这看起来像:

    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
    

相关问题