(一)树结构---基础
导语
- 本章都是对树的一些基本概念的区分，是学习树数据结构的基础，对树已经很了解可以直接跳过
- 为了整体逻辑框架的完整性，所以笔者没有学习完和不懂的地方只写了标题和做了注释，以后回补上
- 结点的关系，双亲，孩子和祖先等并没有进行介绍，不解的自行百度，在文中叶子结点的空孩子有时会以#或T做标识，在相应部分会作说明
- 笔者所有书写皆为自己学习相关学习资料的心得，若有错误之处，欢迎留言指正
1.树的概念
- 树
树是n(n≥0)个结点的有限集。
- 结点
1.这个树中每个元素都称之为结点
2.结点的度：每个结点所拥有的子树数量
3.根据结点度的数量划分为叶子结点(度为0)和非终端结点(度≠0)
4.非终端结点中除了根节点(度=2)，其余又称内部节点或分支结点(1≤度≤2)
- 树的度
1.树中结点最大的度：max(结点度)
2.由于我们研究是主要是二叉树，而二叉树每个节点的度只能为0、1或2，所以二叉树树的度也只能为0，1或2
- 结点层与树的深度
1.结点层：以根节点为第一层，根据子树依次类推，非空二叉树中，第i层最多有ni-1（i≥1）个结点
2.树的深度：结点层最大的叶子结点的层为树的深度：max(叶子结点层)
2.二叉树
1.二叉树定义
每个结点最多有两个子树，即二叉树中不存在度大于2的结点。
2.满二叉树(完美二叉树)
深度为n(n>0)的满二叉树有2n-1个结点
满二叉树
2.完全二叉树
深度为n(n>0)的非空二叉树,第1层到n-1层为满二叉树，第n层从右向左缺失若干结点的树。即叶子结点层的所有结点都在最左边。
完全二叉树
3.完满二叉树
除了叶子结点，任意结点的度都为2的二叉树；即除了叶子节点，其他结点都需要有两个孩子。
完满二叉树
4.区别与联系
1.三种二叉树的关系：
二叉树结构图
2.上图中即为完全二叉树又为完满二叉树的例子
完全二叉树&&完满二叉树
5.最优二叉树(哈夫曼树)
5.1. 相关概念
- 任意两个结点的路径长度：从一个结点到另一个结点需要走过的分支数目
- 树的路径长度：从根节点到每个结点的路径长度之和
- 结点的带权路径：从该结点到树根之间的路径长度与结点上权的乘积
- 树的带权路径长度：树中所有叶子结点的带权路径长度之和
5.2.构造最优二叉树
- 思路：权值越大，路径越短，距离根节点越近。
1. 取权值最小的两个叶子构造其双亲(双亲的权值为两个叶子结点权值之和)
2. 取剩下的叶子结点中权值最小的叶子结点，和之前构造的双亲再构成其双亲
3. 重复2中的步骤，直至所有叶子结点都被构造到树中 - 例子：有四个叶子结点A，B，C，D分别权值为7，5，2，4；求其构成的哈夫曼树？
1.权值最小的C,D两个叶子节点先构成双亲V1，V1权值为6
2.剩余叶子结点中权值最小结点B与V1构成双亲V2，V2权值为11
3.最后一个结点7与V2构成双亲V3，也是该最优二叉树的根结点
最优二叉树 - 应用：
- 在某些算法判断中，利用哈夫曼树可以得到最佳的判断算法，书上的例子是：某学校学生根据考试成绩给学生评级为不及格(score<60)，及格(60≤score<70)，良(70≤score<90)，优(score≥90);
每一分数段的学生数比例为权值，若判断设置合理程度，关系到数据所经过的比较次数，如何得到最小的比较次数，提高判断的效率
PS：笔者没有对哈夫曼树，哈夫曼编码进行深入探究，若想深入理解的，请翻阅相关资料。
3.查找二叉树
- 此处的二叉树概念是基于对二叉树的查找而产生的二叉树定义，第二部分是根据二叉树本身的结构区分的不同二叉树。
1.二分搜索树(二叉顺序树、二叉查找树)
1.左子树的所有结点都小于它的根结点
2.右子树的所有结点都大于它的根结点
3.它的左右子树也满足二分搜索树的性质
在本文第二部分介绍二叉树中所有纯数字的图皆为二分搜索树
2.平衡二叉树
1.首先：平衡二叉树是二分搜索树，所以平衡二叉树必须满足二分搜索树的性质
2.其次：任何结点的左子树的深度和右子树的深度之差(平衡因子)的绝对值不超过1
平衡二叉树和非平衡二叉树
3.B树与B+树
4.红黑树
- 红黑树是基于二分搜索树，所以满足二分搜索树的性质
- 红黑树性质：
1.每个结点或为黑色，或为红色
2.根结点为黑色
3.每个叶子结点为黑色的(红黑树中叶子结点指空结点NIL)
4.如果一个结点是红色的，那他的孩子结点为黑色
5.从任意一个结点到叶子结点，经过的黑色结点是一样的红黑树特点
1.红黑树严格意义上来说并不是平衡二叉树，仅对于黑结点来说，为黑绝对平衡的二叉树(即平衡满二叉树)
2.红黑树与2-3树(2-3-4树)的性质类似
3.红黑树的统计性能更优(增删查改综合的平均性能)
红黑树
PS:具体介绍:
4.二叉树的遍历
-
以下面没有循序(不满足二分搜索树)的满二叉树为例，实现下面遍历
无序满二叉树
4.1.按遍历根结点的顺序划分(打印根结点的顺序)
1.从树的根结点A开始遍历，序号和箭头代表遍历过程中经过结点的先后顺序，
2.不管哪种遍历，对于一个二叉树来说，一定会先经过根结点，左子树，根结点，右子树，根结点
3.每一个结点都会经过三次，叶子结点默认经过两次空子结点。
按根结点划分遍历
1.前序遍历
- 遍历顺序：第一次经过根结点的时候打印：
打印顺序：根结点，左子树，根结点，右子树，根结点
遍历结果：a，b，d，h，i，e，j，k，c，f，l，m，g，n，p
2.中序遍历
- 遍历顺序：第二次经过根结点的时候打印：
打印顺序：根结点，左子树，根结点，右子树，根结点
遍历结果：h，d，i，b，j，e，k，a，l，f，m，c，n，g，p
3.后序遍历
- 遍历顺序：第三次经过根结点的时候打印：
打印顺序：根结点，左子树，根结点，右子树，根结点
遍历结果：h，i，d，j，k，e，b，l，m，f，n，m，g，c，a
4.2.按层遍历划分
按层遍历是指从左向右，从第一层到最高层依次遍历，即从根结点所在层到最高的叶子结点所在层
层序遍历顺序
遍历顺序：根结点，...，内部结点，...，叶子结点
遍历结果：a，b，c，d，e，f，g，h，i，j，k，l，m，n，p
若使用一维数组存储二叉树结构，数据在存储的顺序就是按层遍历顺序
