【408数据结构与算法】—树和二叉树（二十七）
一、树的定义
树的定义
- 树是n(n>=0)个结点的有限集。
- 若n=0;称为空树
若n>0;则它满足如下两个条件
- 有且仅有一个特定的称为根的结点
- 其余结点可分为m(m>=0)个互不相交的有限集T1，T2,T3……Tm.其中每一个集合本身又是一棵树，并称为根的子树。
树是n个结点的有限集，显然，树的定义时一个递归的定义
树的其他集合
二、树的基本术语
- 结点：数据元素以及指向子树的分支
- 根结点：非空树中无前驱结点的结点
- 结点的度：结点拥有的子树数
- 树的度：树内各结点的度的最大值
- 叶子： 度=0。终端结点
- 分支结点：度≠0。非终端结点，根结点以外的分支结点称为内部结点
- 结点的子树称为该结点的孩子，该结点称为孩子的双亲
- 兄弟结点：如果几个结点有共同的前驱结点，我们把这些结点叫做兄弟结点
- 堂兄弟结点：若两个结点的双亲结点在同一层，我们把这两个结点叫做堂兄弟结点
- 结点的祖先：从根结点到该结点所经分支上的所有结点
- 结点的子孙：以某结点为根的子树中的任一结点
- 树的深度：树中结点的最大层次
- 有序树：树中的结点的各子树从左至右有次序（左边的为第一个孩子）
- 无序树：树中结点的各子树无次序
- 森林：是m（m>=0）棵互不相交的树的集合把根结点删除树就变成了森林
- 一棵树可以看成是一个特殊的森林。给森林中的各子树加上一个双亲结点，森林就变成了树。
- 树一定是森林，但森林不一定是树
三、树结构和线性结构的比较
四、二叉树的定义
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点：
1、每个节点最多有两棵子树，即不存在超过度为2的节点。
2、二叉树的子树有左右之分，且左右不能颠倒。
3、二叉树可以是空集合，根可以有空的左子树或空的右子树。
注意：二叉树不是树的特殊情况，他们是两个概念
- 二叉树结点的子树要区分左子树和右子树，即使只有一棵树也要进行区分，说明他是左子树，还是右子树。
- 树当结点只有一个孩子时，就无序区分他是左子树还是右子树，因此二者是不同的，这是二叉树与树的主要区别
也就是二叉树每个结点位置或者说次序都是固定的，可以是空，但是不可以说他没有位置，而树的结点位置是相对于别的结点来说的，没有别的结点时，他就为所谓左右了。
思考：具有3个结点的二叉树可能有几种不同的形态？普通树呢？
二叉树有五种形态：
树有两种形态：
二叉树的五种形态
五、二叉树的抽象数据类型定义
二叉树常用的基本操作
六、二叉树的性质
七、两种特殊的二叉树
❤️满二叉树
满二叉树：一棵深度为 k且有2^k-1个结点的二叉树称为满二叉树
特点：
- 每一层上的结点数都是最大结点数（即每层都满）
- 叶子结点全部在底层
- 对满二叉树进行编号
编号规则：从根结点开始，自上而下，自左而右；每一结点位置都有元素
思考：下图中的二叉树是满二叉树吗？
- 满二叉树在同样深度的二叉树中结点个数最多
- 满二叉树在同样深度的二叉树中叶子结点个数最多
❤️❤️完全二叉树
深度为k的具有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。
判断下列是否是二叉树
注意：在满二叉树中，从最后一个结点开始，连续去掉任意一个结点，即使一棵完全二叉树，注意一定是连续去掉
特点：
- 叶子只能分布在层次最大的两层上
- 对任一结点，如果其右子树的最大层次为i,则其左子树的最大层必为i或i+1
八、二叉树的存储结构
实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素
例：二叉树结点数值采用顺序存储结构，如图所示，画出二叉树的表示图
二叉树的顺序存储特点：
最坏情况：深度为K的且有K个结点的单支树需要长度为2^k-1的一维数组
特点：结点间关系蕴含在其存储位置中，浪费空间，适于存满二叉树和完全二叉树
二叉树的链式存储结构
在n个结点的二叉链表中，有n+1个空指针域
空指针数目=2n-(n-1)=n+1
三叉链表
