python - 在 python 中返回树的预排序列表

Question

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

代码是：

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

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

非常感谢，

Answer 1

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

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

是一个包含三个元素的元组，而不是一个列表。递归调用也将返回元组，因此您将结束一个元组的元组。

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

尝试这样的事情：

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

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

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

Answer 2

只需使用not运算符来反转您的结果Is_EmptyBinTree(T)：

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

None如果没有显式返回其他值，则所有函数都会返回。

Answer 3

列一个列表并递归返回。

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