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

Question

我正在尝试遍历下面代码中创建的二叉树。准确地说，二叉树是一个类，应该包括调用另一个名为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()

我再次修改了代码 我已经完成了代码，但我肯定这不是遍历二叉树的最佳方法。 我在我的类中定义了一个名为-traverse()-的方法，并返回了一个节点列表按顺序（一开始不是按顺序的，所以我使用了sort()方法）。然后我在生成器inorder()函数中对此列表进行了循环，以产生其中的元素。 欢迎您提出所有意见以优化代码。 请基于此代码中的特定Tree类推荐适当的解决方案。

- msc87

Answer 1

也许我有所遗漏，但是我不确定为什么在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

- FatalError

---

我尝试创建一个字典，以便能够追踪我已经生成的节点。问题是，当一个节点有左叶和右叶时，我只能检查左叶，而右叶则被忽略了。 - msc87

Answer 2

我对你的想法感到非常困惑。首先，在这段代码中实际上并没有任何字典，我不理解你为什么引入了全局变量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()

- Francis Avila

---

谢谢你的帮助，但是你建议的代码不起作用。我想使用生成器来实现它。而且这个树没有任何索引。这段代码的主要部分是由我的老师创建的，我应该完成它。 - msc87

我已经添加了一个清晰通过的测试。而不是tree有一个索引，而是你的tree()函数需要一个可索引(真正可切片)的序列来创建树。在这里__iter__是一个生成器，就像你请求的那样。 - Francis Avila