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程序设计有所帮助。

(0)

相关推荐

  • python 平衡二叉树实现代码示例

    平衡二叉树: 在上一节二叉树的基础上我们实现,如何将生成平衡的二叉树 所谓平衡二叉树: 我自己定义就是:任何一个节点的左高度和右高度的差的绝对值都小于2 如图所示,此时a的左高度等于3,有高度等于1,差值为2,属于不平衡中的左偏 此时的处理办法就是: 将不平衡的元素的左枝的最右节点变为当前节点, 此时分两种情况: 一.左枝有最右节点 将最右节点的左枝赋予其父节点的右枝 二.左枝没有最右节点, 直接将左枝节点做父级节点,父级节点做其右枝 如图所示,图更清楚些. 可能会有疑问,为什么这样变换? 假定

  • python数据结构之二叉树的遍历实例

    遍历方案   从二叉树的递归定义可知,一棵非空的二叉树由根结点及左.右子树这三个基本部分组成.因此,在任一给定结点上,可以按某种次序执行三个操作:   1).访问结点本身(N)   2).遍历该结点的左子树(L)   3).遍历该结点的右子树(R) 有次序:   NLR.LNR.LRN 遍历的命名 根据访问结点操作发生位置命名:NLR:前序遍历(PreorderTraversal亦称(先序遍历))  --访问结点的操作发生在遍历其左右子树之前.LNR:中序遍历(InorderTraversal)

  • Python二叉树的镜像转换实现方法示例

    本文实例讲述了Python二叉树的镜像转换实现方法.分享给大家供大家参考,具体如下: 问题描述 操作给定的二叉树,将其变换为源二叉树的镜像. 思路描述 1. 代码比文字更直观 2. 文字描述:新建一个二叉树,利用递归法,将源二叉树上的左节点赋值到新二叉树的右节点,将源二叉树上的右节点赋值到新二叉树的左节点. Python代码 # 方式1:生成新的镜像二叉树 def getMirrorBST(self, root): if root == None: return newTree = treeNo

  • python数据结构之二叉树的建立实例

    先建立二叉树节点,有一个data数据域,left,right 两个指针域 复制代码 代码如下: # -*- coding: utf - 8 - *- class TreeNode(object): def __init__(self, left=0, right=0, data=0):        self.left = left        self.right = right        self.data = data 复制代码 代码如下: class BTree(object):

  • Python编程把二叉树打印成多行代码

    题目描述 从上到下按层打印二叉树,同一层结点从左至右输出.每一层输出一行. 思路: 1.把每层节点的val值用list存好 2.把每层节点存好: ①计算当层节点的个数,这样就保证下一步每层的结点都被pop光 ②然后依次弹出从左到右的每个节点,然后在list中加入该节点对应的左结点.右节点(如果存在的话) 代码如下: class TreeNode(): def __init__(self,x): self.val = x self.left = None self.right = None def

  • python实现的二叉树定义与遍历算法实例

    本文实例讲述了python实现的二叉树定义与遍历算法.分享给大家供大家参考,具体如下: 初学python,需要实现一个决策树,首先实践一下利用python实现一个二叉树数据结构.建树的时候做了处理,保证建立的二叉树是平衡二叉树. # -*- coding: utf-8 -*- from collections import deque class Node: def __init__(self,val,left=None,right=None): self.val=val self.left=l

  • Python实现重建二叉树的三种方法详解

    本文实例讲述了Python实现重建二叉树的三种方法.分享给大家供大家参考,具体如下: 学习算法中,探寻重建二叉树的方法: 用input 前序遍历顺序输入字符重建 前序遍历顺序字符串递归解析重建 前序遍历顺序字符串堆栈解析重建 如果懒得去看后面的内容,可以直接点击此处本站下载完整实例代码. 思路 学习算法中,python 算法方面的资料相对较少,二叉树解析重建更少,只能摸着石头过河. 通过不同方式遍历二叉树,可以得出不同节点的排序.那么,在已知节点排序的前提下,通过某种遍历方式,可以将排序进行解析

  • python数据结构之二叉树的统计与转换实例

    一.获取二叉树的深度 就是二叉树最后的层次,如下图: 实现代码: 复制代码 代码如下: def getheight(self):        ''' 获取二叉树深度 '''        return self.__get_tree_height(self.root) def __get_tree_height(self, root):        if root is 0:            return 0        if root.left is 0 and root.righ

  • Python利用前序和中序遍历结果重建二叉树的方法

    本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字. 这道题比较容易,前序遍历的结果中,第一个结点一定是根结点,然后在中序遍历的结果中查找这个根结点,根结点左边的就是左子树,根结点右边的就是右子树,递归构造出左.右子树即可.示意图如图所示: 利用前序和中序遍历的结果重建二叉树 Python代码: # coding: utf-8 ''

  • Python实现二叉树的常见遍历操作总结【7种方法】

    本文实例讲述了Python实现二叉树的常见遍历操作.分享给大家供大家参考,具体如下: 二叉树的定义: class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None 二叉树的前序遍历 递归 def preorder(root,res=[]): if not root: return res.append(root.val) preorder(root.left,res) preorder

随机推荐