前5篇博客写的都是线性结构,对于有层级结构的数据需要用树形结构来描述
本章的重要知识点
核心一句话
线性结构中一个结点至多只有一个直接后继,树形结构一个结点可以有一个或多个直接后继
看图即可,你要能区分出来哪些是树,哪些不是树
深度
树的相关术语,一定要一开始就明确清晰,后面才好学习
官方概念:二叉树是n(n≥0)个元素的有限集合,该集合或者为空,或者由一个根及两棵互不相交的左子树和右子树组成,其中左子树和右子树也均为二叉树。二叉树的任一结点都有两棵子树(它们中的任何一个都可以是空子树
),并且这两棵子树之间有次序关系,交换位置就成为一棵不同的二叉树。
左子树和右子树,也有的叫做左孩子和右孩子
二叉树五种基本形态,方块表示子树
性质1:二叉树第i(i≥1)层上至多有2^i-1^个结点。
不需要死记硬背,实际需要的时候画一个二叉树就可以求出来了
性质2:深度为k(k≥1)的二叉树至多有2^k^-1个结点
依旧可以推导出来 深度为1的二叉树 结点最多为1 深度为2的二叉树 结点最多为3 深度为3的二叉树 结点最多为7 深度为k的二叉树 结点最多为2^k^-1
性质3:对任何一棵二叉树,若度数为0的结点(叶结点)个数为n~0~,度数为2的结点个数为n~2~,则n~0~ = n~2~+1
这个性质需要稍微推导一下 先回答一个问题,你知道树的度数,怎么计算树的结点数 例如 树的度数为2,结点树为几,这个不难想象,会出现如下情况
看到这里不难发现,存在一个公式为 树的度数+1=树的结点树 那么我们开始推导上述公式 假设 二叉树的0度,1度,2度结点个数为n~0~,n~1~,n~2~,结点总数为T T = n~0~+n~1~+n~2~ 树的度数+1 = T 树的度数怎么求?n~0~0+n~1~1+n~2~2 是树的度数 继续n~0~0+n~1~1+n~2~2 +1 = T = n~0~+n~1~+n~2~ ===> 2n~2~+1=n~0~+n~2~ ===>n~0~=n~2~+1
好了,上述过程,争取看明白吧
性质4:含有n个结点的完全二叉树的深度为?log~2~n?+1
这个地方引出了一个新的概念
完全二叉树
说明什么是完全二叉树之前,需要理解什么是满二叉树
满二叉树 深度为k(k≥1)且有2^k^-1个结点的二叉树称为满二叉树
完全二叉树
如果对满二叉树按从上到下,从左到右的顺序编号,并在最下一层删除去部分结点(删除最后一层仍有结点),如果删除的这些结点的编号是连续的且删除的结点中含有最大编号的结点,那么这棵二叉树就是完全二叉树
注意 ?x?
这个符号,表示不大于x的最大整数
教材中,给了几个范例,偷懒我用一下
关于性质4的证明,有兴趣的自行研究一下吧
性质5:如果将一棵有n个结点的完全二叉树按层编号
,按层编号是指:将一棵二叉树中的所有n个结点按照从第一层到最大层,每层从左到右的顺序依次标记为1,2,....,n。则对任意编号i(1≤i≤n)的结点A有:
(1)若i=1,则结点A是根;若i>1,则A的双亲编号为 ?i/2?
。(注意 ?x?
这个符号,表示不大于x的最大整数)
(2)若2*i>n,则结点A既无左孩子,也无右孩子;否则A的左孩子的编号为2*i。
(3)若2*i+1>n,则结点A无右孩子;否则,A的右孩子编号为2*i+1;
这个性质5有点意思,先验证一下
所以这个性质稍微配合着图看一下就可以完美学会
二叉树也是两类存储结构:顺序存储和链式存储
先看顺序存储结构
这个地方对于初学者你来说,理解即可
对一棵完全二叉树上的所有结点按层编号,然后按照编号存储到一维数组里面即可。
书中有个比较好的例子了,直接截图,理解一下
重点是下面,如果一个树不是完全二叉树咋办
教材中给的方案是,添加虚拟结点,说白了,就是凑成完全二叉树,不过注意这种解决方案缺点就是浪费空间
二叉树的链式存储,记住常用的叫做 二叉链表 和 三叉链表 即可,其他的在自考和期末考试中不是重点部分,选择性的看不到吧。
这个有点意思了,是考试的重点,但是不是叫你写代码哦~而是手动遍历。 请注意,二叉树遍历有六种可能,我们核心关注三种
分别是
直接看图解释吧,先画一个二叉树
为了解决遍历问题,你要先划分好区域,找到左子树、右子树还有根
先序遍历走起
中序遍历走起
后序遍历走起
这种题就多练就可以啦~
当然还有一种需要会,叫做二叉树的按层遍历,这个就比较简单了,自行学习一下就可以掌握
二叉树遍历在自考中是一个比较重要的题目,来几道真题吧
在评论区写上你的答案吧
更多内容,欢迎关注 https://dwz.cn/r4lCXEuL