华子目录
- 1.树和二叉树的定义
- 1.1树的定义
- 1.2树的基本术语
- 1.3线性结构和树结构
- 1.4二叉树的定义
- 2.二叉树的性质和存储结构
- 2.1二叉树的性质
- 2.2二叉树的存储结构
- 2.2.1顺序存储
- 2.2.2链式存储
- 2.3遍历二叉树
- 2.4大作业:二叉树的基本操作
- 2.4.1代码思路(仅供参考,思路不限):
- 2.4.2代码实践(递归写法)
1.树和二叉树的定义
1.1树的定义
树
是n
(n≥0
)个结点
的有限集
,它
或为空树
(n=0
);或为非空树
,对于非空树T
:
- 有且仅有
一个
称之为根
的结点
- 除
根结点
以外的其余结点
可分为m
(m>0
)个互不相交
的有限集T₁,T₂,…,Tm
,其中每一个结点本身
又是一棵树
,并且成为根
的子树
图 1(A)
是使用树结构
存储的集合{A,B,C,D,E,F,G,H,I,J,K,L,M}
的示意图
。对于数据A
来说,和数据B、C、D
有关系;对于数据B
来说,和E、F
有关系。这就是“一对多
”的关系。将具有“一对多
”关系的集合
中的数据元素
按照图 1(A)
的形式进行存储
,整个存储形状
在逻辑结构
上看,类似于实际生活中倒着的树
(图 1(B)
),所以称这种存储结构
为“树型
”存储结构
1.2树的基本术语
结点
:树
中的一个独立单元
。包含一个数据元素
和若干
指向其子树
的分支
,如图1(A)
中的A、B、C、D
等结点的度
:结点
拥有的子树数
成为结点的度
。例如,A的度
为3
,C的度
为1
,F的度
为0
树的度
:树的度
是树内各结点度
的最大值
。图1(A)
所示的树的度
为3
叶子
:度
为0
的结点
称为叶子
或终端结点
。结点K、L、F、G、M、I、J
都是树的叶子
。叶子结点
无孩子
非终端结点
:度不为0
的结点
称为非终端结点
。双亲和孩子
:结点的子树
的根
称为该结点
的孩子
,相应地,该结点
称为孩子
的双亲
。例如,B的双亲
为A
,B的孩子
有E和F
兄弟
:同一个双亲
的孩子
之间互称兄弟
。例如,H、I和J
互为兄弟
祖先
:从根
到该结点
所经分支上
的所有结点
。例如,M的祖先
为A、D和H
子孙
:以某结点
为根
的子树中
的任一结点
都称为该结点的子孙
。如B的子孙
为E、K、L和F
层次
:结点
的层次
从根
开始定义起
,根
为第一层
,根的孩子
为第二层
。堂兄弟
:双亲
在同一层
的结点
互为堂兄弟
。例如,结点G
与E、F、H、I、J
互为堂兄弟
树的深度
:树中结点
的最大层次
称为树的深度
或高度
。图1(A)
所示的树的深度
为4
有序树
和无序树
:如果将树中结点
的各子树
看成从左至右
是有次序
的(即不能互换
),则称该树
为有序树
,否则称为无序树
。在有序树
中最左边
的子树
的根
称为第一个孩子
,最右边
的称为最后一个孩子
森林
:是m
(m≥0
)棵互不相交
的树的集合
。把树的根节点
删除,它的子树们
就构成了森林
1.3线性结构和树结构
线性结构 | 树结构 |
---|---|
第一个数据元素无前驱 | 根结点无双亲 |
最后一个数据元素无后继 | 叶子结点无孩子 |
其他数据元素一个前驱一个后继 ,一对一 | 其他结点(中间结点)一个双亲多个孩子 ,一对多 |
1.4二叉树的定义
二叉树
是n
(n≥0
)个结点
所构成的集合
,它或为空树
(n=0
);或为非空树
,对于非空树
:
- 有且仅有
一个
称之为根的结点
- 除
根结点以外
的其余结点
分为两个
互不相交的子集T₁和T₂
,分别称为T
的左子树
和右子树
,且T₁
和T₂
本身又都是二叉树
二叉树
与树
一样具有递归性质
,二叉树
与树
的区别主要有以下两点
二叉树
每个结点至多
只有两棵子树
(即二叉树
中不存在度大于2
的结点
)二叉树
的子树
有左右之分
,其次序不能任意颠倒
二叉树的递归定义
表明二叉树
或为空
,或是由一个根结点
加上两棵
分别称为左子树
和右子树
的、互不想交
的二叉树
组成。由于这两棵子树
也是二叉树
,则由二叉树
的定义,它们也可以是空树
。由此,二叉树
可以有5种
基本形态,如下图所示:
树的基本术语
是都适用于二叉树的
2.二叉树的性质和存储结构
2.1二叉树的性质
二叉树
具有以下几个性质:
二叉树
还有两种特殊的形态
:满二叉树
和完全二叉树
二叉树
中除了叶子结点
,每个结点
的度
都为2
,则此二叉树
称为满二叉树
。
二叉树
中除去最后一层节点
为满二叉树
,且最后一层
的结点
依次从左到右
分布,则此二叉树
被称为完全二叉树
。
满二叉树
一定是完全二叉树
,完全二叉树
不一定是满二叉树
2.2二叉树的存储结构
二叉树的存储结构
有两种
,分别为顺序存储
和链式存储
2.2.1顺序存储
二叉树
的顺序存储
,指的是使用顺序表
(数组
)存储二叉树
。需要注意的是,顺序存储
只适用于完全二叉树
。换句话说,只有完全二叉树
才可以使用顺序表存储
。因此,如果我们想顺序存储普通二叉树
,需要提前将普通二叉树
转化为完全二叉树
普通二叉树
转完全二叉树
的方法很简单
,只需给二叉树
额外添加一些节点
,将其"拼凑
"成完全二叉树
即可。如下图所示,左侧
是普通二叉树
,右侧
是转化后
的完全(满)二叉树
解决了二叉树
的转化问题
,接下来我们来学习如何顺序存储完全(满)二叉树
。完全二叉树
的顺序存储
,仅需从根节点
开始,按照层次
依次将树中节点
存储到数组
即可
例如,存储上图
所示的完全二叉树
,其存储状态
如下图
所示:
由此,我们就实现了完全二叉树
的顺序存储
2.2.2链式存储
其实二叉树
并不合适
用数组
存储,因为并不是每个二叉树
都是完全二叉树
,普通二叉树
使用顺序表存储
会存在空间浪费
的现象。接下来介绍二叉树
的链式存储结构
上图
为一颗普通的二叉树
,若将其采用链式存储
,则只需从树的根节点
开始,将各个节点
及其左右孩子
使用链表存储
即可。因此,其对应的链式存储结构
如下图所示:
由上图可知,采用链式
存储二叉树
时,其节点结构
由3部分
构成:
- 指向
左孩子节点
的指针
(Lchild
) - 节点存储的
数据
(data
) - 指向
右孩子节点
的指针
(Rchild
)
其实,二叉树
的链式存储
结构远不止上图所示
的这一种
。例如,在某些实际场景
中,可能会做 “查找某节点的父节点
” 的操作
,这时可以在节点结构
中再添加一个指针域
,用于各个节点
指向其父亲节点
,如下图 所示:
2.3遍历二叉树
- 在
二叉树
的一些应用中,常常要求在树中
查找具有某种特征
的结点
,或者是对树中
的全部结点
逐一处理
,这就提出了一个遍历二叉树
的问题
。遍历二叉树
是指按某一条搜索路径
巡访树中
每个结点
,使得每个结点
均被访问一次
,而且仅被访问一次
。遍历二叉树
是二叉树
最基本的操作,也是二叉树
其他各种操作
的基础
,遍历的实质
是对二叉树
进行线性化
的过程,即遍历的结果
是将非线性结构
的树中结点
排成一个线性序列
。由于二叉树
的每个结点
都有可能有两棵子树
,因而需要寻找一种规律
,以便使二叉树
上的结点
能排列
在一个线性队列
上,从而便于遍历
二叉树
是有3
个基本单元
组成:根节点、左子树、右子树
。因此,若能依次遍历
这三部分
,便是遍历了整个二叉树
。假如L、D、R
分别表示遍历左子树、访问根节点、遍历右子树
,则可有DLR、LDR、LRD、DRL、RDL、RLD
这6种
遍历二叉树的方案
。若限定先左后右
,则只有前3种
情况,分别称之为先(根)序遍历
、中(根)序遍历
和后(根)序遍历
基于二叉树
的递归定义
,可得下述遍历二叉树
的递归算法
定义。
先序遍历二叉树
的操作定义如下:
若二叉树
为空
,则空操作
;否则
(1)访问根节点
;
(2)先序
遍历左子树
;
(3)先序
遍历右子树
。
中序遍历二叉树
操作定义如下:
若二叉树
为空
,则空操作
;否则
(1)中序
遍历左子树
;
(2)访问根节点
;
(3)中序
遍历右子树
。
后序遍历二叉树
的操作定义如下:
若二叉树
为空
,则空操作
;否则
(1)后序
遍历左子树
;
(2)后序
遍历右子树
;
(3)访问根节点
。
例如,上图的二叉树
表示的为表达式:a+b*(c-d)-e/f
先序遍历二叉树
,可得到二叉树
的先序序列
为:-+a*b-cd/ef
中序遍历二叉树
,可得此二叉树
的中序序列
为:a+b*c-d-e/f
后序遍历二叉树
,可得此二叉树
的后序序列
为:abcd-*+ef/-
2.4大作业:二叉树的基本操作
构建
二叉树
(遍历列表按照先序顺序
插入值)
测试案例
的输入列表
为[‘A’,‘B’,‘C’,’#’,’#’,‘D’,‘E’,’#’,‘G’,’#’,’#’,‘F’,’#’,’#’,’#’]
,输出的遍历结果
见下图
二叉树
的生成,需要用以上输入列表的数值哦;对于非递归遍历
,需要用到栈
。
2.4.1代码思路(仅供参考,思路不限):
二叉树
的生成
:
- 构建
结点类
,构建二叉树类
- 输入一个
列表
,然后从列表
中取数
,按照先序顺序
进行递归插入数值
,即先创建根结点
,再左子树
,再右子树
- 首先输入一个
字符
,判断其是否为#
,不是#
的即创建根结点
,该结点
的数值域
为该字符
,继续递归
生成左子树
,输入第二个字符
,判断其是否为#
,不是#
的即生成结点
,是#
的将返回上一层递归
,如此判断递归生成二叉树
二叉树
的遍历
:
- 按照
先序、中序、后序遍历
的顺序
输出字符即可
非递归的遍历
是需要借助栈的
- 拿
中序遍历
的非递归算法思想
来举例:定义一个空栈
,从根结点
开始访问
,若当前节点非空
,则将该节点压栈
并访问其左子树
,循环执行
,直至当前节点
为空
时,取栈顶元素
访问并弹栈
,然后访问其右子树
,再重复如上操作
,直至遍历节点的指针为空
并且栈也为空
2.4.2代码实践(递归写法)
python">class Tree:def __init__(self, item):self.item = itemself.l = Noneself.r = Nonedef llink(self, other): #左连接子节点self.l = otherdef rlink(self, other): # 右连接子节点self.r = otherdef get_depth(self): # 获取深度(递归)if self.l == None:l_depth = 0else:l_depth = self.l.get_depth()if self.r == None:r_depth = 0else:r_depth = self.r.get_depth()return max(l_depth, r_depth) + 1def get_len(self): # 获取节点数(递归)if self.l == None:l_len = 0else:l_len = self.l.get_len()if self.r ==None:r_len = 0else:r_len = self.r.get_len()return l_len + r_len + 1def show_first(self): # 先序遍历(递归)print(self.item, end=" ")if self.l != None:self.l.show_first()if self.r != None:self.r.show_first()def show_mid(self): # 中序遍历(递归)if self.l != None:self.l.show_mid()print(self.item, end=" ")if self.r != None:self.r.show_mid()def show_last(self): # 后序遍历(递归)if self.l != None:self.l.show_last()if self.r != None:self.r.show_last()print(self.item, end=" ")def create(x):try:tmp = next(x)if tmp == "#":returnroot = Tree(tmp)root.llink(create(x))root.rlink(create(x))return rootexcept:passtree_list = ['A', 'B', 'C', '#', '#', 'D', 'E', '#', 'G', '#', '#', 'F', '#', '#', '#']
it = iter(tree_list)
root = create(it)# 先序遍历
print(root.show_first())# 中序遍历
print(root.show_mid())# 后序遍历
print(root.show_last())