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数据分析删除重复值(Python3实现从排序数组中删除重复项算法分析)
- python操作json库(Python将json文件写入ES数据库的方法)
- python怎么转换jar包(利用python脚本如何简化jar操作命令)
- 12步轻松搞定python装饰器(Python3.5装饰器典型案例分析)
- python序列定义(详解Python3序列赋值、序列解包)
- python自动解数独教学(Python判断有效的数独算法示例)
- 时间日期python实例(Python之时间和日期使用小结)
- python常用的切片操作(使用python PIL库实现简单验证码的去噪方法步骤)
- python怎么在csv修改数据(python 编写输出到csv的操作)
- python默认缩进设置(不归路系列:Python入门之旅-一定要注意缩进!!!推荐)
- python解析excel例子(Python玩转Excel的读写改实例)
- python装饰器语法与应用(python装饰器简介---这一篇也许就够了推荐)
- 如何用python在微信里自动回复(Python实现微信自动好友验证,自动回复,发送群聊链接方法)
- python端口扫描脚本测试(Python实现的IP端口扫描工具类示例)
- python csv文件读取方法(对python读取zip压缩文件里面的csv数据实例详解)
- python 3.10 循环语法(Python3.4学习笔记之常用操作符,条件分支和循环用法示例)
- 智能手表兼容Windows和Android 无需充电挑战苹果(智能手表兼容Windows和Android)
- 一天一冲也算表 麦步,一款待机 21 天的智能手表体验评测(一天一冲也算表)
- 魅族智能手表充电座曝光 Type-C 接口,线座分离设计(魅族智能手表充电座曝光)
- 华为 Watch GT2 Pro 智能手表曝光,新增支持无线充电(华为WatchGT2)
- vivo首款智能手表来了 也有血氧饱和度监测,一次充电18天续航(vivo首款智能手表来了)
- 你知道 七夕 的真正含义吗(你知道七夕的真正含义吗)
热门推荐
- docker部署go项目(Gogs+Jenkins+Docker 自动化部署.NetCore的方法步骤)
- python指定参数教程(详解Python传入参数的几种方法)
- vue界面自动生成(Vue中实现3D标签云的详细代码)
- javascript如何建立一个静态变量(JavaScript中子函数访问外部变量的3种解决方法)
- dedecms数据库备份地址(dedecms搬家时出现数据库导入失败的解决方法)
- 怎么查看云服务器的配置(云服务器配置参数如何选择)
- docker shell教学(docker安装rockerChat设置聊天室的详细步骤)
- python虚拟环境和包使用教程(在win10和linux上分别安装Python虚拟环境的方法步骤)
- mpp数据库的客户端工具(xampp默认mysql数据库root密码的修改)
- php无法读取txt文件(php写入txt乱码的解决方法)
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9