python – 使用生成器在BST上执行inorder树遍历

发布时间：2020-12-20 11:42:25 所属栏目：Python 来源：网络整理

导读：所以给出以下内容： 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 STr

所以给出以下内容：

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

解决方法

inorder(t.left)只创建生成器对象,它实际上并不运行它.您需要迭代并生成每个子生成器生成的值：

# 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

通过在Python 3.3中引入new syntax,这变得更加清晰：

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!