导语

• 本章都是对树的一些基本概念的区分，是学习树数据结构的基础，对树已经很了解可以直接跳过
• 为了整体逻辑框架的完整性，所以笔者没有学习完和不懂的地方只写了标题和做了注释，以后回补上
• 结点的关系，双亲，孩子和祖先等并没有进行介绍，不解的自行百度，在文中叶子结点的空孩子有时会以#或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层最多有n^i-1（i≥1）个结点
2.树的深度：结点层最大的叶子结点的层为树的深度：max(叶子结点层)

---

2.二叉树

1.二叉树定义

每个结点最多有两个子树，即二叉树中不存在度大于2的结点。

2.满二叉树(完美二叉树)

深度为n(n>0)的满二叉树有2ⁿ-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，也是该最优二叉树的根结点

  
  最优二叉树

• 应用：

1. 在某些算法判断中，利用哈夫曼树可以得到最佳的判断算法，书上的例子是：某学校学生根据考试成绩给学生评级为不及格(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. 红黑树性质：
    1.每个结点或为黑色，或为红色
    2.根结点为黑色
    3.每个叶子结点为黑色的(红黑树中叶子结点指空结点NIL)
    4.如果一个结点是红色的，那他的孩子结点为黑色
    5.从任意一个结点到叶子结点，经过的黑色结点是一样的

3. 红黑树特点
    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
若使用一维数组存储二叉树结构，数据在存储的顺序就是按层遍历顺序