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。

尝试这样的事情:

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))