使用递归反序列化 Python 中的二叉树

Question

我正在尝试编写序列化和反序列化二叉树的代码。我成功地序列化了树，但是，我发现反序列化很困难。（我知道有很多解决方案。但是，我更喜欢在查找之前自己学习）

考虑下面的树

      __1
     /   \
    2     3
   / \     \
  4   5     6

我的序列化模块输出

[1, 2, 4, None, None, 5, None, None, 3, None, 6, None, None]

我的代码是

def serialize(root):
    nodes = list()
    stack = [root]
    while len(stack):
        node = stack.pop()
        if node is not None: 
            nodes.append(node.value)
            if node.right: 
                stack.append(node.right)
            else:
                nodes.append(None)
            if node.left: 
                stack.append(node.left)
            else:
                nodes.append(None)
                
    return nodes

如何在没有递归的情况下反序列化？
是否有反序列化的递归版本？
我做的树遍历，有名字吗？
是否有序列化的递归版本？

任何对 material 有帮助的建议也非常感谢。

Answer 1

你真的应该只问一个问题，所以我只关注反序列化：

How do I deserialize without recursion?

就像您的 non-recursive 序列化解决方案一样，您需要一个堆栈。您还需要知道当前值是用于左侧还是右侧 child。您可以从 preceding 输入值知道这一点。它是 None，这意味着下一个值总是对 child。如果没有，那么总是说明我们刚刚创建了一个parent节点，当前值大约是它的leftchild.

此外，当您从根的虚拟 parent 节点开始时，该算法会更容易一些，因此树被构建为其 left-side 子树：

def deserialize(data):
    stack = []
    prev_value = 1  # dummy value, can be anything, but not None
    parent = node = Node(prev_value)  # dummy node, whose left child will be the result
    for value in data:
        if value is None:
            if node.left is not None or prev_value is None:
                # Current None is about right child. Go up...
                node = stack.pop()
                while node.right is not None:
                    node = stack.pop()
        else:  # going down...
            stack.append(node)
            if prev_value is None:  # ...after going up
                node.right = Node(value)
                node = node.right
            else:
                node.left = Node(value)
                node = node.left
        prev_value = value
    return parent.left

Is there a recursive version of the deserialization?

是的，有，而且需要的代码更少：

def deserialize(data):
    it = iter(data)

    def recur():
        value = next(it)
        return None if value is None else Node(value, recur(), recur())
    
    return recur()

以上代码假定您有一个 Node 构造函数，它接受（可选）参数作为其 left 和 right 属性：

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

The tree traversal I did, does it have a name?

是的，这是一个preorder traversal。

Is there a recursive version of the serialization?

是的。试一试。如果您在创建此类版本时遇到问题，请专门针对该问题提出一个单独的问题。

使用递归反序列化 Python 中的二叉树

Deserializing a Binary Tree in Python with recursion

tree

binary-tree

traversal

binary-search-tree

data-structures