python 二叉树的深度遍历(python 将有序数组转换为二叉树的方法)
类别:脚本大全 浏览量:1366
时间:2021-10-27 10:49:31 python 二叉树的深度遍历
python 将有序数组转换为二叉树的方法题目:将[0,1,2,3,4,5,6,7,8,9,10]存储到二叉树,原数组有序,转换为二叉排序树。
二叉排序树的特点:当前节点的左子树上的所有节点都小于该节点,右子树上的所有节点都小于该节点。
二叉排序也称为二叉查找树。
我的实现思路:
取有序数组的中间节点作为根节点,将数组分为左右两个部分,对左右两个子数组做相同的操作,递归的实现。
图示:
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 |
我们调用前面写的三种遍历方法看一看,我们构造的树是否正确:
|
#将[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) |
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持开心学习网。
原文链接:https://www.jianshu.com/p/b7492d68a39f
您可能感兴趣
- python开发网站github(使用 Python 玩转 GitHub 的贡献板推荐)
- python装饰器使用说明(详解Python装饰器)
- 超简单使用Python换脸实例(超简单使用Python换脸实例)
- python抽奖转盘代码(详解python--模拟轮盘抽奖游戏)
- ocr公式识别python(初探利用Python进行图文识别OCR)
- python创建hbase命名空间(python使用phoenixdb操作hbase的方法示例)
- python直接查询mongodb(pymongo中聚合查询的使用方法)
- pythonmatplotlib绘制立体图形(python3使用matplotlib绘制散点图)
- 虚拟环境python详细教程(python创造虚拟环境方法总结)
- python 的常用工具(Python静态类型检查新工具之pyright 使用指南)
- 怎么python爬取网页图片(详解Python静态网页爬取获取高清壁纸)
- python用pyqt5制作登录界面(python3+pyqt5+itchat微信定时发送消息的方法)
- python做学生成绩系统(python学生管理系统)
- python怎么实现链表(Python实现数据结构线性链表单链表算法示例)
- python中赋值语句规则(Python动态赋值的陷阱知识点总结)
- python如何判断是否为回文数(对python判断是否回文数的实例详解)
- 今天 3月13日,31年前,一个英雄少年感动了中国(今天3月13日31年前)
- 你好,新成理人丨成都理工大学2019级新生开学典礼隆重举行(新成理人丨成都理工大学2019级新生开学典礼隆重举行)
- 这部民警编演的红色话剧,讲述了一个不断追寻的故事(这部民警编演的红色话剧)
- 日本菜有什么好吃(日本菜有什么好吃的做法)
- 韩国泡菜做法(韩国泡菜的做法步骤)
- 泰国旅游攻略(泰国旅游攻略必去景点)
热门推荐
- dedecms调用原始图(DEDECMS点击图片进入下一页功能实现教程)
- dedecms标签怎么调用(织梦DEDECMS获取当前页面的顶级栏目名称及链接教程)
- html5+canvas动画(解析html5 canvas实现背景鼠标连线动态效果代码)
- vue滚动条滚动事件(vue实现一个滚动条样式)
- pythonturtle库画图代码(用Python中的turtle模块画图两只小羊方法)
- docker无法访问宿主机ip(解决Mac下 docker 无法 ping 通宿主机的问题)
- 程序员职业该如何规划
- 菲律宾云服务器价格(菲律宾云服务器适合用来做什么?)
- c#中SqlBulkCopy的使用
- css中最常用的选择符(CSS 类选择符和ID选择符的区别)
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9