目录
- 把数组放入二叉树
- 1.给定数组为有序数组,需要构造出有序二叉树
- 1.1 树
- 1.2 二叉树
- 1.3把数组放入二叉树
- 1.4使用中序遍历的方式打印二叉树
- 1.5 使用层序遍历的方式打印二叉树
把数组放入二叉树
给定一个有序整数数组arr,要求:
- 给定数组为有序数组,需要构造出有序二叉树
- 使用中序遍历的方式打印该二叉树
- 使用层序遍历的方式打印该二叉树
1.给定数组为有序数组,需要构造出有序二叉树
1.1 树
- 树一种重要的数据结构
- 基本概念:节点、节点关系、节点层次、树的深度
- 结点:树结构的基础,是构成树的基本组成单位
- 结点关系:A是B、C的父母结点,B、C是A的子结点
- 结点层级:从根开始定义起,根为第一层,根的孩子为第二层,以此类推
- 树的深度:树中结点的最大层次数称为树的深度或高度
1.2 二叉树
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5zwHlxHx-1586513283395)(attachment:binary_tree.jpg)]
- 每个结点最多有两颗子树
- 左子树和右子树是有顺序的,次序不能任意颠倒
- 即使树中某结点只有一棵子树,也要区分它是左子树还是右子树
1.3把数组放入二叉树
- 取数组中间元素作为根结点,将数组分为左右两部分
- 对数组左右两部分用递归方法分别构建左右子树
- 递归算法
复制代码
1
2
3
4
5
6class BiNode: def __init__(self): self.data = None #结点数据 self.lchild = None #左子树结点 self.rchild = None #右子树结点
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#将有序数组转换为二叉树 def array_to_tree(arr, start, end): """将有序数组转换成二叉树 arr:有序数组 start:数组起点索引 end:数组结尾索引 """ root = None #初始化根结点数据 if end >= start: root = BiNode() #创建树实例 mid = (start + end + 1)//2 #取中点数据索引 root.data = arr[mid] #树的根结点诶数组中间元素 root.lchild = array_to_tree(arr, start, mid - 1) #使用递归方式用左半部分数组构建root的左子树 root.rchild = array_to_tree(arr, mid+1, end) #使用递归方式用右半部分数组构建root的右子树 else: root = None return root
结果图示
1.4使用中序遍历的方式打印二叉树
- 中序遍历:按照左子树->根节点->右子树的顺序访问 (一种深度优先遍历)
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19#使用中序遍历的方式打印二叉树 def print_tree_midorder(root): """使用中序遍历的方式打印二叉树内容 root:二叉树根结点 """ if root == None: #判断是否为空 return #使用递归方式,遍历root节点的左子树 if root.lchild != None: print_tree_midorder(root.lchild) #遍历root节点 print(root.data, end = ' ') #使用递归方式,遍历root节点右子树 if root.rchild != None: print_tree_midorder(root.rchild)
复制代码
1
2
3arr = list(range(1,11)) arr
复制代码
1
2[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
复制代码
1
2root = array_to_tree(arr, 0, len(arr)-1)
复制代码
1
2
3print('树的中序遍历结果为:', end = '') print_tree_midorder(root)
复制代码
1
2树的中序遍历结果为:1 2 3 4 5 6 7 8 9 10
对照树结构产看遍历结果
1.5 使用层序遍历的方式打印二叉树
- 层序遍历:按照层从小到大,同一层从左到右依次遍历(广度优先遍历)
- 在遍历一个结点的同时记录其子节点信息,然后按照这个记录的顺序访问结点数据
- 可以采用队列存储当前遍历到的结点的子节点
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#使用层序遍历的方式打印二叉树 from collections import deque #载入队列结构,deque是双向队列 def print_tree_layer(root): """使用层序遍历的方式打印二叉树内容 root:二叉树根结点 """ if root == None: return queue = deque() #创建队列实例 #树根结点进队列 queue.append(root) while len(queue)>0: p = queue.popleft() #出队 #访问当前节点 print(p.data, end = ' ') #如果该节点左孩子不为空,则入队列 if p.lchild != None: queue.append(p.lchild) #如果该节点右孩子不为空,则入队列 if p.rchild != None: queue.append(p.rchild)
复制代码
1
2
3arr = list(range(1,11)) arr
复制代码
1
2[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
复制代码
1
2root = array_to_tree(arr, 0, len(arr)-1)
复制代码
1
2
3print('树的层序遍历结果为:', end = '') print_tree_layer(root)
复制代码
1
2树的层序遍历结果为:6 3 9 2 5 8 10 1 4 7
对照树结构产看遍历结果
更多内容请访问:
链接1:
链接2
最后
以上就是包容小熊猫最近收集整理的关于[小白系列]Python实现逻辑树、遍历树(深度优先以及广度优先),以非计算机专业的角度学习把数组放入二叉树的全部内容,更多相关[小白系列]Python实现逻辑树、遍历树(深度优先以及广度优先),以非计算机专业内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复