将二叉树转换为 Python 级别顺序的列表

Question

我还没有找到任何相关的问题。

所以问题是：给定一个不完整的二叉树，比如树的根，我如何将它转换成 Python 中的级别顺序的列表，使得空节点（其中缺少节点级别）在列表中表示为“None”。

比如我有这棵树：

     1
   /   \
 4      0.52
/ \      / \
   2.5

我想获取以下列表：

[1, 4, 0.52, None, 2.5, None, None]

通过使用像这样的函数：

list = toList(root)

此外，我的树结构如下：

class TreeNode:

def __init__(self, value, isLeaf):

    self.left = None
    self.right = None
    self.value = value
    self.isLeaf = isLeaf

并从另一个 post 那里借用解决方案（到没有 'None' 发生的列表）：

def toList(root):
    node_list = []
    thislevel = [root]
    while thislevel:
        nextlevel = list()
        
        for n in thislevel:
            # print(n.value)
            node_list.append(n.value)

            if n.left: 
                nextlevel.append(n.left)
            if n.right: 
                nextlevel.append(n.right)
        # print
        thislevel = nextlevel
    return node_list

my_list = toList(root)
print(my_list)

到目前为止，这给出了以下内容：

[1, 4, 0.52, 2.5]

我被困在这里，不知道如何正确地将 'None' 插入列表...

谢谢！

Answer 1

您通常使用 queue 对图进行广度优先迭代。这是一个先进先出的数据结构。您首先将根添加到队列中，然后当队列中有项目时，弹出最旧的一个，将其添加到结果中并将其子元素推送到队列中。如果你这样做不是为了小输入，python 的 collections.deque 比这里使用的列表更有效：

class TreeNode:
    def __init__(self, value, isLeaf):
        self.left = None
        self.right = None
        self.value = value
        self.isLeaf = isLeaf

        
def breadth_first(t):
    q = [t]
    while q:
        current = q.pop(0)
        yield current.value if current else None
        if current and not current.isLeaf:
            q.extend([current.left, current.right])
        
            
t = TreeNode(1, False)
t.left = TreeNode(4, False)
t.right = TreeNode(0.52, False)
t.left.right = TreeNode(0.2

list(breadth_first(t))
# [1, 4, 0.52, None, 0.25, None, None]

将二叉树转换为 Python 级别顺序的列表

Convert binary tree to a list with level order in Python

python

list

binary-tree

breadth-first-search