1. 概要

本文简要介绍二叉树的序列化处理和反序列化处理及对应的python实现。

二叉树通常为了方便而以一维数组（比如说python list）的格式进行存储，二叉树的序列化（serialization）就是指将二叉树转换成列表或者一维数组的形式。实际使用的时候再由列表的形式变换回二叉树的格式，这个就是反序列化（de-serialization）。

序列化和反序列化是各种复杂的数据结构的实际存储和使用时都需要碰到的问题。

2. 用一维数组表示二叉树

一个常见的误解是将二叉树进行层序遍历展开就得到了二叉树的一维数组表示。其实不是，单纯地对二叉树进行得到的列表无法还原成原始的二叉树。

二叉树的序列化(serialization)与反序列化(de-serialization)-LMLPHP

上图这个不完全的二叉树直接进行层序遍历得到的是[1,2,-3,-5,4]，实际上它的一维数组表示为[1,2,-3,-5,null,4,null]。

用一维数组表示二叉树的基本规则是(为了方便，记该数组为a，0-indexing，并且采用python slicing的方式表示子数组)：

(1) a[0]表示根节点

(2) a[2**k-1 : 2**(k+1)-1]表示层k(1,2,...)的节点（假定根节点位于层0）

(3) 每一层中的节点按从左到右排列

(4) 不存在（作为完全二叉树应该有但是实际上不存在）的节点用None或者Null填充

(5) 最后的连续的None可以去除

3. python实现

3.1 二叉树节点的表示

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

每个二叉树的节点最都有两个子节点，分别为左子节点和右子节点。以上类定义中，分别用left和right指向左子节点和右子节点。

3.2 串行化的python实现

实现思路：to be added

def binTree2Lst(root):
    """ 
    binary tree serialization.
    Convert a binary tree with "root" as its root to a list.
    """
    if root == None:
        return []

    nodeLst = [root]
    valLst  = []
    
    while len(nodeLst) > 0:
        curNode = nodeLst.pop()
        if curNode != None:
            nodeLst.insert(0,curNode.left)
            nodeLst.insert(0,curNode.right)        
            valLst.append(curNode.val)
        else:
            valLst.append(None)

    # Throw away the trailing 'None'
    while valLst[-1] == None:
        valLst.pop()

    return valLst

3.3 反串行化的python实现

实现思路：to be added

def lst2bintree(x:List[int]) -> Optional[TreeNode]:
    if len(x) == 0: # []
        root = None
    if x[0] == None: # [None]
        root = None

    x.reverse() # For the convenience of utilizing x.pop()
    nodeLoL = []        
    root = TreeNode(x.pop())
    nodeLoL.append([root])
    k = 0
    while(1):
        #print('k = {0}, {1}'.format(k, x))
        newLayer = []
        for node in nodeLoL[k]:
            #print(node.val)
            if node == None:
                pass
            else:
                if len(x) == 0:
                    break
                tmp = x.pop()
                if tmp != None:
                    newNode = TreeNode(tmp)
                    node.left = newNode
                    newLayer.append(newNode)

                if len(x) == 0:
                    break
                tmp = x.pop()
                if tmp != None:
                    newNode = TreeNode(tmp)
                    node.right = newNode
                    newLayer.append(newNode)

        if len(x) == 0:
            break
        nodeLoL.append(newLayer)
        k += 1
        
    return root

3.4 测试

    x   = [3,9,20,None,None,15,7]
    root = lst2bintree(x)
    print(root.val)
    print(root.left.val)
    print(root.right.val)
    print(root.left.left)
    print(root.left.right)    
    print(root.right.left.val)
    print(root.right.right.val)  
    print(binTree2Lst(root))

    x = [1,2,-3,-5,None,4,None]
    root = lst2bintree(x)
    print(binTree2Lst(root))

运行结果如下：

笨牛慢耕