python - 如何从先序树遍历生成的数组重建二叉树

Question

我被要求实现一个前序树遍历函数，该函数应该返回一个表示树的数组，然后我被要求实现一个函数来从我以前的函数返回的数组中重建树。就像从一台 pc 发送二叉树，然后在接收端接收和重建它一样。重要的是数据应该只传输一次，所以我不能使用标准的预序和中序组合。

在我的解决方案中，打印每个节点，然后将其添加到包含所有打印节点的数组中，如果节点没有左子树，它将打印并添加字母“L”，如果树没有右子树，它将打印并将字母“R”添加到数组。

那部分很简单，但是，我不知道如何在接收端重建树。任何帮助或想法将不胜感激。

这是我为发送部分所做的:

class TreeNode(object):
"""This class represents a tree."""

    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def send(arr_tree, data):
    print(data)
    arr_tree.append(data)

def send_sub_tree(arr_tree, node):
    send(arr_tree, node.data)
    if node.left is None:
        send(arr_tree, "L")
    else:
        send_sub_tree(arr_tree, node.left)
    if node.right is None:
        send(arr_tree, "R")
    else:
        send_sub_tree(arr_tree, node.right)

if __name__ == '__main__':
    tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, 
    TreeNode(6), TreeNode(7)))
    received_tree = []
    send_sub_tree(received_tree, tree)
    reconstructed_tree = reconstruct_tree(received_tree)

编辑:

我已经成功地实现了一些类似的东西，但是它很乱而且不能完美地重建发送的部分:

def reconstruct_tree(arr_tree):
    node = TreeNode(arr_tree[0])
    print(node.data)

    if arr_tree[1] == "L" and arr_tree[2] == "R":
        if len(arr_tree) > 3 and arr_tree[3] != "L" and arr_tree[3] != "R":
            node.right = reconstruct_tree(arr_tree[3:])

    else:
        return node
    if arr_tree[1] != "L":
        node.left = reconstruct_tree(arr_tree[1:])
        return node

return node

Answer 1

这里是你如何做到的。我还将您的函数移到类中，重命名它们并进行了一些修改:

class TreeNode(object):
    """This class represents a tree."""
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def to_list(self):
        return [self.data] + (
                self.left.to_list() if self.left else ["L"]
            ) + (
                self.right.to_list() if self.right else ["R"]
            )

    @staticmethod
    def from_list(lst):
        def recurse(it):
            try:
                data = next(it)
            except StopIteration: # Only happens if list is incomplete
                return
            if data == 'L' or data == 'R':
                return
            return TreeNode(data, recurse(it), recurse(it))
        return recurse(iter(lst))

tree = TreeNode(1, 
            TreeNode(2, 
                TreeNode(4),
                TreeNode(5)
            ), 
            TreeNode(3, 
                TreeNode(6),
                TreeNode(7)
            )
        )
lst = tree.to_list()
print(lst)
# Reverse operation
recovered_tree = TreeNode.from_list(lst)
# Make that a list again to see if it is the same tree
lst2 = recovered_tree.to_list()
print(lst2) # Same as lst

查看它在 repl.it 上运行

请注意，您也可以对右边的 child 使用“L”，或者对左边的 child 使用“R”，因为数组中的位置已经毫无疑问地表明是哪个 child 。一个特殊符号就够了。