数据结构第四章树和二叉树，期末不挂科指南，第6篇

章节简介

前5篇博客写的都是线性结构，对于有层级结构的数据需要用树形结构来描述

本章的重要知识点

1. 理解有关树的基本概念和二叉树的基本概念
2. 掌握二叉树的存储结构以及遍历方法
3. 掌握树的存储结构以及树、森林、二叉树的相互转换方法
4. 梳理掌握哈夫曼树构造方法和哈夫曼编码的设计方法

树的基本概念

核心一句话

线性结构中一个结点至多只有一个直接后继，树形结构一个结点可以有一个或多个直接后继

认识树

看图即可，你要能区分出来哪些是树，哪些不是树

树的相关术语

1. 结点的度：树上任意结点所拥有的子树的数目称为该结点的度
   

2. 叶子：度为0的结点称为叶子或者终端结点
   

3. 树的度：一棵树中所有结点的度的最大值称为该树的度，就是把所有结点的度求和

4. 结点的层次：从根算起，根的层次为1，其余结点的层次为其双亲的层次加1
   

5. 树的高度：一棵树中所有结点层次数的最大值称为该树的高度或深度

6. 还有一些小概念：有序树、无序树

树的相关术语，一定要一开始就明确清晰，后面才好学习

二叉树

官方概念：二叉树是n(n≥0)个元素的有限集合，该集合或者为空，或者由一个根及两棵互不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。二叉树的任一结点都有两棵子树（它们中的任何一个都可以是空子树），并且这两棵子树之间有次序关系，交换位置就成为一棵不同的二叉树。

左子树和右子树，也有的叫做左孩子和右孩子

二叉树五种基本形态，方块表示子树

二叉树的基本运算（不写代码，了解重点函数即可）

1. 初始化
2. 求双亲
3. 求左孩子
4. 求右孩子
5. 建二叉树
6. 先序遍历！！！
7. 中序遍历！！！
8. 后序遍历！！！
9. 层次遍历！！！
   先序遍历，中序遍历，后序遍历在考试中一般不要求手写代码，但是需要你能通过一棵树结构，输出最终的结果，这个博客结尾给大家看一下例题

二叉树性质（很重要，细碎知识点很多）

性质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有点意思，先验证一下

所以这个性质稍微配合着图看一下就可以完美学会

二叉树存储结构

二叉树也是两类存储结构：顺序存储和链式存储

先看顺序存储结构

这个地方对于初学者你来说，理解即可

对一棵完全二叉树上的所有结点按层编号，然后按照编号存储到一维数组里面即可。

书中有个比较好的例子了，直接截图，理解一下

重点是下面，如果一个树不是完全二叉树咋办

教材中给的方案是，添加虚拟结点，说白了，就是凑成完全二叉树，不过注意这种解决方案缺点就是浪费空间

二叉树的链式存储，记住常用的叫做 二叉链表 和 三叉链表 即可，其他的在自考和期末考试中不是重点部分，选择性的看不到吧。

二叉树的遍历

这个有点意思了，是考试的重点，但是不是叫你写代码哦~而是手动遍历。
请注意，二叉树遍历有六种可能，我们核心关注三种

分别是

1. 先序遍历
2. 中序遍历
3. 后序遍历

直接看图解释吧,先画一个二叉树

为了解决遍历问题，你要先划分好区域，找到左子树、右子树还有根

先序遍历走起

1. 访问根结点 （==根结点在开头==）
2. 先序遍历左子树
3. 先序遍历右子树

中序遍历走起
4. 中序遍历左子树
5. 访问根结点 （==根结点在中间==）
6. 中序遍历右子树

后序遍历走起

1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根结点（==根结点在后头==）

这种题就多练就可以啦~

当然还有一种需要会，叫做二叉树的按层遍历，这个就比较简单了，自行学习一下就可以掌握