Python實現(xiàn)的序列化和反序列化二叉樹算法示例

更新時間：2019年03月02日 11:57:55 作者：hustfc

這篇文章主要介紹了Python實現(xiàn)的序列化和反序列化二叉樹算法,結(jié)合實例形式分析了Python二叉樹的構(gòu)造、遍歷、序列化、反序列化等相關(guān)操作技巧,需要的朋友可以參考下

本文實例講述了Python實現(xiàn)的序列化和反序列化二叉樹算法。分享給大家供大家參考，具體如下：

題目描述

請實現(xiàn)兩個函數(shù)，分別用來序列化和反序列化二叉樹

序列化二叉樹

先序遍歷二叉樹

  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:]

結(jié)果：

root = TreeNode(11)
root.left = TreeNode(2)
root.right = TreeNode(3)
series = Solution().Serialize(root)
print(series)
>>>11,2,$,$,3,$,$

反序列化

先構(gòu)建根節(jié)點，然后左節(jié)點，右節(jié)點，同樣是遞歸

注意由于使用的是字符串的表示形式，可以先轉(zhuǎn)化為list，

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

然后再處理就不需要將大于10的數(shù)字轉(zhuǎn)換過來了：

  def getValue(self, s, sIndex):  #處理超過10的數(shù)字，將數(shù)字字符轉(zhuǎn)變?yōu)閿?shù)字
    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

下面是反序列化的遞歸函數(shù)：

  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的數(shù)字，將數(shù)字字符轉(zhuǎn)變?yōu)閿?shù)字
    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

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進階經(jīng)典教程》

希望本文所述對大家Python程序設(shè)計有所幫助。

您可能感興趣的文章: