1. python 将有序数组转换为二叉树的方法

     更新时间:2019年03月26日 09:18:26   作者:DKider   我要评论

    这篇文章主要介绍了python 将有序数组转换为二叉树的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

    题目:将[0,1,2,3,4,5,6,7,8,9,10]存储到二叉树,原数组有序,转换为二叉排序树。

    二叉排序树的特点:当前节点的左子树上的所有节点都小于?#23186;?#28857;,右子树上的所有节点都小于?#23186;?#28857;。

    二叉排序也称为二叉查找树。

    我的实现思路:

    取有序数组的中间节点作为根节点,将数组分为左右两个部分,对左右两个子数组做相同的操作,递归的实现。

    图示:

    1

    2

    3

    代码实现:

    def array_to_bitree(array):
      #判断arr是否为空
      if len(array)==0:
        return BiTNode(array[0])
      mid=len(array)//2 # 有序数组的中间元素的下标
      #print(mid)
      #start=0 # 数组第一个元素的下标
      #end=-1 # 数组最后一个元素的下标
      if len(array)>0:
        #将中间元素作为二叉树的根
        root=BiTNode(array[mid])
        #如果左边的元素个数不为零,则递归调用函数,生成左子树
        if len(array[:mid])>0:
          root.left_child = arrayToBiTree(array[:mid])
        #如果右边的元素个数不为零,则递归调用函数,生成左子树
        if len(array[mid+1:])>0:
          root.right_child = arrayToBiTree(array[mid+1:])
      return root

    我们调?#20204;?#38754;写的三种遍历方法看一看,我们构造的树是否正确:

    #将[0,1,2,3,4,5,6,7,8,9,10]存储到二叉树
    if __name__ == '__main__':
      #先构造一个有序数组、链表
      arr=[]
      for i in range(10):
        arr.append(i)
      print(arr)
      #调用函数
      BT=arrayToBiTree(arr)
      #前序遍历二叉树
      print("前序")
      print_tree_pre_order(BT)
      # 中序遍历二叉树
      print("中序")
      print_tree_mid_order(BT)
      # 后序遍历二叉树
      print("后序")
      print_tree_after_order(BT)

    输出:

    根据这三种遍历结果可以判断出二叉树的结构,结果和前面的是一样的,代码如下:

    #定义二叉树结点类型
    class BiTNode:
      """docstring for BiTNode"""
      def __init__(self,arg):
        self.data = arg
        self.left_child = None
        self.right_child = None
    
    #前序遍历
    def print_tree_pre_order(root):
      #先判断二叉树是否为空
      #if root.left_child is None and root.right_child is None:
      if root is None:
        return root
      #先根
      print(root.data)
      #再左
      if root.left_child is not None:
        print_tree_pre_order(root.left_child)
      #再右
      if root.right_child is not None:
        print_tree_pre_order(root.right_child)
    
    #中序遍历二叉树
    def print_tree_mid_order(root):
    
      #先判断二叉树是否为空,当左右节点都为空时
      if root is None:
        return
      #中序遍历 左根右
      #遍历左子树
      if root.left_child is not None:
        print_tree_mid_order(root.left_child)
      #遍历根节点
      print(root.data)
      #遍历右子树
      if root.right_child is not None:
        print_tree_mid_order(root.right_child)
    
    #后序遍历
    def print_tree_after_order(root):
      #先判断二叉树是否为空
      if root is None:
        return root
      #再左
      if root.left_child is not None:
        print_tree_after_order(root.left_child)
      #再右
      if root.right_child is not None:
        print_tree_after_order(root.right_child)
      #先根
      print(root.data)
    
    def array_to_bitree(array):
      #判断arr是否为空
      if len(array)==0:
        return BiTNode(array[0])
      mid=len(array)//2 # 有序数组的中间元素的下标
      #print(mid)
      #start=0 # 数组第一个元素的下标
      #end=-1 # 数组最后一个元素的下标
      if len(array)>0:
        #将中间元素作为二叉树的根
        root=BiTNode(array[mid])
        #如果左边的元素个数不为零,则递归调用函数,生成左子树
        if len(array[:mid])>0:
          root.left_child = array_to_bitree(array[:mid])
        #如果右边的元素个数不为零,则递归调用函数,生成左子树
        if len(array[mid+1:])>0:
          root.right_child = array_to_bitree(array[mid+1:])
      return root
    
    
        
    
    #将[0,1,2,3,4,5,6,7,8,9,10]存储到二叉树
    if __name__ == '__main__':
      #先构造一个有序数组、链表
      arr=[]
      for i in range(9):
        arr.append(i)
      print(arr)
      #调用函数
      BT=array_to_bitree(arr)
      #前序遍历二叉树
      print("前序")
      print_tree_pre_order(BT)
      # 中序遍历二叉树
      print("中序")
      print_tree_mid_order(BT)
      # 后序遍历二叉树
      print("后序")
      print_tree_after_order(BT)

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

    相关文章

    • 基于python list对象中嵌套元组使用sort时的排序方法

      基于python list对象中嵌套元组使用sort时的排序方法

      下面小编就为大家分享一篇基于python list对象中嵌套元组使用sort时的排序方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
      2018-04-04
    • python实现unicode转中文及转换默认编码的方法

      python实现unicode转中文及转换默认编码的方法

      这篇文章主要介绍了python实现unicode转中文及转换默认编码的方法,结合实例形式分析了Python针对Unicode编码操作的相关技巧及编码转换中的常见问题解决方法,需要的朋友可以参考下
      2017-04-04
    • 老生常谈Python startswith()函数与endswith函数

      老生常谈Python startswith()函数与endswith函数

      下面小编就为大家带来一篇老生常谈Python startswith()函数与endswith函数。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
      2017-09-09
    • 关于你不想知道的所有Python3 unicode特性

      关于你不想知道的所有Python3 unicode特性

      我的读者知道我是一个?#19981;?#30171;骂Python3 unicode的人。这?#25105;?#19981;例外。我将会告诉你用unicode有多痛苦和为什么我不能闭嘴。?#19968;?#20102;两周时间研究Python3,我需要发泄我的失望。在这些责骂中,仍然有有用的信息,因为它教我们如何来处理Python3。如果没有被我烦到,?#25237;?#19968;读吧
      2014-11-11
    • Python解析json文件相关知识学习

      Python解析json文件相关知识学习

      JSON(JavaScript Object Notation) 是一种轻?#32771;?#30340;数据?#25442;?#26684;式。接下来通过本文给大家介绍python解析json文件相关知识,对python解析json文件相关知识感兴趣的朋友一起学习吧
      2016-03-03
    • Python的Flask框架应用程序实现使用QQ账号登录的方法

      Python的Flask框架应用程序实现使用QQ账号登录的方法

      利用QQ开放平台的API使用QQ账号登录是现在很多网站都具备的功能,而对于Flask框架来说则有Flask-OAuthlib这个现成的轮子,这里我们就来看一下Python的Flask框架应用程序实现使用QQ账号登录的方法
      2016-06-06
    • Python实现?#20540;?dict)的迭代操作示例

      Python实现?#20540;?dict)的迭代操作示例

      这篇文章主要介绍了Python实现?#20540;?dict)的迭代操作,结合实例形式分析了Python针对?#20540;?#38190;、值以及键值对等迭代操作实现技巧,需要的朋友可以参考下
      2018-06-06
    • 深入理解Python 关于supper 的 用法和原理

      深入理解Python 关于supper 的 用法和原理

      这篇文章主要介绍了Python 关于supper 的 用法和原理分析,非常不错,具有参考借鉴价值,需要的朋友参考下吧
      2018-02-02
    • Python输出汉字字库及将文字转换为?#35745;?#30340;方法

      Python输出汉字字库及将文字转换为?#35745;?#30340;方法

      这篇文章主要介绍了Python输出汉字字库及将文字转换为?#35745;?#30340;方法,分别用到了codecs模块和pygame模块,需要的朋友可以参考下
      2016-06-06
    • python 容器总结整理

      python 容器总结整理

      这篇文章主要介绍了python 容器总结整理的相关资料,需要的朋友可以参考下
      2017-04-04

    最新评论

    山东群英会开奖查询
      1. 福建11选5 黑龙江十一选五爱彩乐 青海十一选五开奖走势图 排列三走势图带线 河北快三开奖结果是 发财二肖中特精准资料 双色球历史开奖号码(按出球顺序) 内蒙古快三根号 黑龙江11选5的推荐 大乐透开机号码2019099 江苏体彩11选5 曾道人免费资料大全正版2019 天重庆时时彩开奖历史 电子游戏作文600字议论文 秒速飞艇官方投注平台