returns python 中一棵树的预购列表

Question

我是 python 的新手，我正在尝试编写一个函数来递归 return 树的预排序列表。我可以得到它来获取预购列表，但是，它带有大量来自与基本案例的递归交互的不需要的空列表。

密码是：

def BinPreOrder(T):
    if Is_EmptyBinTree(T):
        return []
    else:
        return BinRoot(T), BinPreOrder(Left(T)), BinPreOrder(Right(T))

如何获得仅包含每个节点值的列表的输出（没有空列表等）？

非常感谢，

Answer 1

只需使用 not 运算符来反转 Is_EmptyBinTree(T):

的结果

def BinPreOrder(T):
    if not Is_EmptyBinTree(T):
        return BinRoot(T), BinPreOrder(Left(T)), BinPreOrder(Right(T))

所有函数 return None 如果没有其他值明确 returned。

Answer 2

我假设你想要一个简单的列表，而不是一个元组的元组作为你的答案。第一个问题是

BinRoot(T), BinPreOrder(Left(T)), BinPreOrder(Right(T))

是三个元素的元组，不是列表。递归调用也会 return 元组，所以你将结束元组的元组。

第二个问题是您的结果中出现了所有 None。正如一些人已经指出的那样，python 默认情况下总是 return None，所以你必须明确避免 None。

尝试这样的事情：

def BinPreOrder(T):
    if not Is_EmptyBinTree(T):
        answer = [BinRoot(T)] 
        left = BinPreOrder(Left(T))
        if left is not None:
           answer.extend(left) 
        right = BinPreOrder(Right(T))
        if right is not None:
           answer.extend(right)
        return answer

编辑：有一种更短、更清晰的方法可以做到这一点。不要让它 return None 用于空子树，而是让它 return 一个空列表。然后你可以连接三个列表。我专注于解决您的代码的问题，而不是考虑问题本身。抱歉

def BinPreOrder(T):
    if Is_EmptyBinTree(T): return []
    return [BinRoot(T)] + BinPreOrder(Left(T)) + BinPreOrder(Right(T))

Answer 3

创建一个列表并return递归。

def BinPreOrder(T):
    ans=[]
    if T is not None:
        ans.append(T.val)
        ans.extend(BinPreOrder(T.lelt))
        ans.extend(BinPreOrder(T.right))
    return ans

returns python 中一棵树的预购列表

returns the preorder list of a tree in python

python

tree

return

empty-list

preorder