使用生成器对 BST 执行中序树遍历

Question

因此给出以下内容：

def inorder(t):
    if t:
        inorder(t.left)
        yield t.key
        inorder(t.right)

x = [ n for n in inorder(r) ]

x只包含根节点，为什么？

这是完整的代码；请注意，BST 实现是正确的，它是带有生成器的 inorder() 实现在某种程度上是错误的。

class STree(object):
    def __init__(self, value):
        self.key = value
        self.left = None
        self.right = None

def insert(r, node):
    if node.key < r.key:
        if r.left is None:
            r.left = node
        else:
            insert(r.left, node)
    else:
        if r.right is None:
            r.right = node
        else:
            insert(r.right, node)

def inorder(t):
    if t:
        inorder(t.left)
        yield t.key
        inorder(t.right)


r = STree(10)
insert(r, STree(12))
insert(r, STree(5))
insert(r, STree(99))
insert(r, STree(1))

tree = [ n for n in inorder(r) ]
print tree

Answer 1

inorder(t.left) 只创建生成器对象，实际上运行并没有。您实际上需要 yield 每个子生成器产生的所有值，如下所示：

def inorder(t):
    if t:
        yield from inorder(t.left)
        yield t.key
        yield from inorder(t.right)

请注意，yield from 便捷语法仅在 Python 3.3 中引入，因此如果您使用的是旧版本，则必须显式迭代子生成器：

# Python 2
def inorder(t):
    if t:
        for key in inorder(t.left):
            yield key
        yield t.key
        for key in inorder(t.right):
            yield key

使用生成器对 BST 执行中序树遍历

Using generators to perform an inorder tree traversal on a BST

python

recursion

generator

binary-search-tree