Python实现的序列化和反序列化二叉树算法示例

本文实例讲述了python实现的序列化和反序列化二叉树算法。分享给大家供大家参考，具体如下：

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

序列化二叉树

先序遍历二叉树

  def recursionserialize(self, root):
    series = ''
    if root == none:
      series += ',$'
    else:
      series += (',' + str(root.val))
      series += self.recursionserialize(root.left)
      series += self.recursionserialize(root.right)
    return series
  def serialize(self, root):
    return self.recursionserialize(root)[1:]

结果：

root = treenode(11)
root.left = treenode(2)
root.right = treenode(3)
series = solution().serialize(root)
print(series)
>>>11,2,$,$,3,$,$

反序列化

先构建根节点，然后左节点，右节点，同样是递归

注意由于使用的是字符串的表示形式，可以先转化为list，

print(series.split(','))
>>>['11', '2', '$', '$', '3', '$', '$']

然后再处理就不需要将大于10的数字转换过来了：

  def getvalue(self, s, sindex):  #处理超过10的数字，将数字字符转变为数字
    val = 0
    while ord(s[sindex]) <= ord('9') and ord(s[sindex]) >= ord('0'):
      val = val * 10 + int(s[sindex])
      sindex += 1
    return val, sindex - 1

下面是反序列化的递归函数：

  def deserialize(self, s):
    if self.sindex < len(s):
      if s[self.sindex] == ',':
        self.sindex += 1
      if s[self.sindex] == '$':
        return none
      val, self.sindex = self.getvalue(s, self.sindex)
      treenode = treenode(val)
      self.sindex += 1
      treenode.left = self.deserialize(s)
      self.sindex += 1
      treenode.right = self.deserialize(s)
      return treenode

完整解法

class treenode:
  def __init__(self, x):
    self.val = x
    self.left = none
    self.right = none
class solution:
  def __init__(self):
    self.sindex = 0
  def recursionserialize(self, root):
    series = ''
    if root == none:
      series += ',$'
    else:
      series += (',' + str(root.val))
      series += self.recursionserialize(root.left)
      series += self.recursionserialize(root.right)
    return series
  def serialize(self, root):
    return self.recursionserialize(root)[1:]
  def getvalue(self, s, sindex):  #处理超过10的数字，将数字字符转变为数字
    val = 0
    while ord(s[sindex]) <= ord('9') and ord(s[sindex]) >= ord('0'):
      val = val * 10 + int(s[sindex])
      sindex += 1
    return val, sindex - 1
  def deserialize(self, s):
    if self.sindex < len(s):
      if s[self.sindex] == ',':
        self.sindex += 1
      if s[self.sindex] == '$':
        return none
      val, self.sindex = self.getvalue(s, self.sindex)
      treenode = treenode(val)
      self.sindex += 1
      treenode.left = self.deserialize(s)
      self.sindex += 1
      treenode.right = self.deserialize(s)
      return treenode

更多关于python相关内容感兴趣的读者可查看本站专题：《python数据结构与算法教程》、《python加密解密算法与技巧总结》、《python编码操作技巧总结》、《python函数使用技巧总结》、《python字符串操作技巧汇总》及《python入门与进阶经典教程》

希望本文所述对大家python程序设计有所帮助。