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

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 中，重命名了它们，并做了一些修改：

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

上查看运行

请注意，您也可以将 "L" 用于 right-side child，或者将 "R" 用于左侧，因为数组中的位置已经没有了怀疑 child 是什么意思。一个特殊符号就够了。

Answer 2

让我们考虑一个通用算法，使用维基百科的前序遍历示例：

F, B, A, D, C, E, G, I, H.

让我们标记一个 None 为空子树：

A = [F, B, A, None, None, D, C, None, None, E, None, None, G, None, I, H, None]

现在我们从根开始：

F
-> have a left subtree so insert B
   descend
-> have a left subtree so insert A
   descend
-> have no left subtree
-> have no right subtree
   return
-> have a right subtree so insert D
   descend
-> have a left subtree so insert C
   descend
-> have no left subtree
-> have no right subtree
   return
-> have a right subtree so insert E
   descend
-> have no left subtree
-> have no right subtree
   return

但是我们如何知道return到哪个索引和节点呢？一种方法是从 return 是要使用的下一个索引的节点调用递归函数（请记住此处和下面的示例中 i 是局部变量）：

f(node, i):
  # left subtree
  if A[i]:
    insertLeft(A[i])
    i = f(node.left, i + 1)
  else:
    i = i + 1

  #right subtree
  if A[i]:
    insertRight(A[i])
    i = f(node.right, i + 1)
  else
    i = i + 1

  return i

让我们应用到我们的示例中：

A = [F, B, A, None, None, D, C, None, None, E, None, None, G, None, I, H, None]

f(F, 1)
  insertLeft(B)

  i = f(B,2)
        insertLeft(A)

        i = f(A,3)
              i = 4
              i = 5
              return 5

        insertRight(D)

        i = f(D,6)
              insertLeft(C)

              i = f(C,7)
                    i = 8
                    i = 9
                    return 9

              insertRight(E)

              i = f(C,10)
                    i = 11
                    i = 12
                    return 12

              return 12

        return 12

  insertRight(G)  # A[12]

  etc...

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

How to reconstrunct a binary tree from an array produced by preorder tree traversal

python

algorithm

binary-tree