使用生成器进行二叉树有序遍历

一尘不染

使用生成器进行二叉树有序遍历

algorithm

描述

我希望二叉树是可迭代的，这样我就可以循环访问每个节点一次。此外，inorder还包括一个生成器函数，它返回Iterator并因此满足Iterable合同要求。但是我下面的代码没有产生每个节点，而是产生了根节点，在这种情况下是A。我做错了什么？

码

from collections import namedtuple

Node = namedtuple('Node', 'data, left, right')

root = Node('A',
        Node('B', Node('D', None, None), Node('E', None, None)),
        Node('C', None, Node('F', None, None)))

class BinaryTree(object):
    def __init__(self, root=None):
        self.root = root

    def __iter__(self):
        return self.inorder(self.root)

    def inorder(self, node):
        if node is None:
            return
        if node.left is not None:
            self.inorder(node.left)
        yield node
        if node.right is not None:
            self.inorder(node.right)

bt = BinaryTree(root)            
for node in bt:
    print node.data

阅读 752

2020-07-28

共1个答案

一尘不染

问题是您调用self.inorder(node.left)，但不对结果做任何事情，结果，代码仅被执行（延迟执行得很好，这意味着未执行），并且运行时环境继续到下一行。

您需要通过传播（即 重新生成 ）由以下调用生成的元素来解决该问题inorder：

    def inorder(self, node):
        if node is None:
            return
        if node.left is not None:
            for x in self.inorder(node.left) :
                # you need to *re-yield* the elements of the left and right child
                yield x
        yield node
        if node.right is not None:
            for x in self.inorder(node.right) :
                yield x

2020-07-28