树的编码

#二叉树
根据二叉树的性质可以存在不同的编码方式

  1. 完全二叉树 (Complete Binary Tree)
    树除了最后一层，每一层的节点都是满的。按照层次遍历，输出各个节点即可。在解码时，检查层节点是否是满的。如果不是，说明是最后一层。

    顺道提一下，如何判断一颗树是完全二叉树呢？
    可利用每层节点都是满的性质，采用层次遍历，将每一节点的左右孩子都存在队列中。一旦出现为空的节点，其后的所有节点也一定都是空的.

    1
    queue = deque(root)
while queue and queue[0] not None:
    node = queue.popleft()
    queue.append(node.left)
    queue.append(node.right)
while queue and queue[-1] is None:
    queue.popleft()
return not queue

  2. 二叉搜索树
    由于二叉搜索树中序遍历的值是有序的。我们知道，对于任意二叉树，可使用中序和(前序&后续)任意一种，即可完成解码。
    从而在编码时，只需编码前序或者后续任意一种即可。
    解码时，通过preorder首元素进行二分，递归建立树，如果预先处理next数组，复杂度为O(n)
    代码可参考：

  3. 满二叉树(Full Tree)
    每个节点只有0或2个孩子。采用前序遍历，并用特殊符号标记是否存在孩子即可，和后续的普通二叉树方法类似。
  4. 普通二叉树
    可以采用任意一种遍历方式(前中后)，使用 # 标记空孩子，空格’ ‘隔开各个节点。解码时，需要注意 # 标记的空孩子。
    1
    # use preorder travase to visit the tree
# mark NULL node as #, space '_' to seperate each node
#        5
#    3      4
#  1   6       7
#
# 编码结果为: 5 3 1 # # 6 # # 4 # 7 # #
def encode(node):
    if not node:
        return '# '
    s = str(node.val) + ' '
    s += encode(node.left)
    return s+encode(node.right)

def decode(s, i):
    if i[0] == len(s):
        return None
    space_idx = s.find(' ', i[0])
    val = s[i[0]:space_idx]
    i[0] = space_idx+1
    if val == '#':
        return None
    root = TreeNode(val)
    root.left = decode(s, i)
    root.right = decode(s, i)
    return root

此种方式对于空节点较少的情形较好，对于空节点较多的场景，可以进行优化。
使用特殊字符 ! 标记节点存在孩子， 当不存在孩子时，什么也不用做。
如果只存在一个孩子，另外一个孩子仍然需要使用#标记。
参考之前给出的树的例子，编码长度大幅减少。

1
# use preorder travase to visit the tree
# mark NULL node as #, space '_' to seperate each node
# if node has childs, use !
#        5
#    3      4
#  1   6       7
#
# 编码结果为 5 ! 3 ! 1 6 4 ! # 7
def encode2(node):
    if not node:
        return '# '
    s = str(node.val) + ' '
    if node.left or node.right:
        s += '!'
        s += encode2(node.left)
        s += encode2(node.right)
    return s


def decode2(s, i):
    if i[0] == len(s):
        return None
    space_idx = s.find(' ', i[0])
    val = s[i[0]:space_idx]
    i[0] = space_idx+1
    if val == '#':
        return None
    root = TreeNode(val)
    if i[0] < len(s) and s[i[0]] == '!':
        i[0] += 1
        root.left = decode2(s, i)
        root.right = decode2(s, i)
    return root

#多叉树
编码方式和二叉树类似，可采用前序遍历，递归创建，使用#标记子节点结束。

1
def encode3(node):
    if not node:
        return ""
    s = str(node.val)+' '
    for child in node.children:
        s += encode3(child)
    s += '#'
    return s


def decode3(s, i):
    if i[0] == len(s):
        return None
    space_idx = s.find(' ', i[0])
    val = s[i[0]:space_idx]
    node = MultiTree(val)
    i[0] = space_idx+1
    while i[0] < len(s) and s[i[0]] != '#':
        node.children.append(decode3(s, i))
    i[0] += 1  # mark
    return node