1. 树的定义

  1. 树是 n(n>=0) 个结点的有限集
    1. n = 0 时称为空树
    2. n > 0 时称为非空树
      1. 一棵树中只有一个特定的结点被称为根结点
      2. 子树互不相交
  2. 树是递归定义的数据结构

image.png

1.1 结点的分类

  1. 结点的度：结点拥有的子树数（分支结点的度>0，叶子结点的度=0）
  2. 树的度：树内各结点的度的最大值（哪个结点的子树最多）
  3. 度为 0 的结点：叶结点，终端结点
  4. 度不为 0 的结点：分支结点

image.png

1.2 结点间关系

  1. 孩子：结点的子树的根。如上图中，B 的孩子是 D ，而不是 G，H，I
  2. 子孙：某结点为根的子树中的任意结点。如上图中，B 的子孙就是 D，G，H，I
  3. 双亲：结点的前驱
  4. 兄弟：同一个双亲的孩子之间是兄弟
  5. 祖先：从根结点到所经分支上的所有结点

image.png

1.3 树的其他相关概念

  1. 结点的层次：从根开始定义，根为第一层，根的孩子为第二层
  2. 堂兄弟：双亲再同一层的结点（如下图的 D，E，F）
  3. 树的深度（高度）：结点的最大层次（如下图为 4）
  4. 有序树：从左至右有顺序，不能互换。否则为无序树
  5. 森林：m（m>=0） 棵不相交的树的集合

image.png

  1. n 个结点的树有 n-1 条边，每一个树中结点总比边多 1 个
  2. 具体的树的性质见《天勤》P133

1.4 树的性质归纳

度为m m叉树
度为m的树，第i层至多有m^(i-1)个结点
高度为h的度为m的树至少有h+m-1个结点

2. 树的抽象数据类型

  1. InitTree(*T); // 构造空树 T
  2. DestroyTree(*T); // 销毁树 T
  3. CreateTree(*T,definition); // 按 definition 中给出树的定义来构造树
  4. ClearTree(T); // 清空树
  5. TreeEmpty(T); // 判断是否是空树
  6. TreeDepth(T); // 返回树的深度
  7. Root(T); // 返回树的根结点
  8. Value(T,cur_e); // 返回 cur_e 这个结点的值
  9. Assign(T,cur_e,value); // 给 cur_e 这个结点赋值为 value
  10. Parent(T,cur_e); // 返回 cur_e 双亲
  11. LeftChild(T,cur_e); // 返回它的左孩子
  12. RightSibling(T,cur_e); // 返回它的右兄弟
  13. InsertChild(*T,*p,i,c); // 插入新子树 c 到 p 指向的第 i 棵子树
  14. DeletChild(*T,*p,i); // 删除 p 指向的第 i 棵子树

3. 树的存储结构

3.1 双亲表示法（从双亲结点的角度看）

该结点包括两个部分：数据域和指针域，其中指针域指示双亲结点的位置
image.png

这是直接利用数组来实现的，其中数组的下标表示结点，数组的元素内容表示其双亲结点的下标
image.png

1. 数据结构

  1. typedef int TElemType;
  3. typedef struct PTNode
  4. {
  5.     TElemType data;
  6.     int parent;
  7. }PTNode;
  9. // PTNode 就是 typedef int money 中的 money
  11. typedef struct
  12. {
  13.     PTNode nodes[MAXSIZE]; // 定义结点数组
  14.     int r,n; // 定义根的位置和结点数 
  15. }

2. 示例图

根结点的双亲域设置为 -1，因为根结点没有双亲
image.png
寻找双亲结点的时间复杂度是 O(1)，而寻找孩子结点则要遍历整个结构

3.2 孩子表示法（从孩子结点的角度看）

  1. 孩子表示法其核心想要处理的对象是孩子结点。
  2. 这种表示法是结合了两种存储结构而成的，分别是顺序表结构和链表结构。
  3. 其中顺序表存储的是所有的结点，每一个结点又链接出该结点所有的孩子结点（注意，不是子孙结点）

如图，顺序表竖直摆放，链表横向摆放。（同一横行的链表都是同一个双亲下的孩子）
image.png

1. 设置的两种数据结构

顺序表结构
image.png

链表结构
image.png

2. 孩子表示法的结构体定义

  1. // 这是孩子结点的数据结构 
  2. typedef struct CTNode
  3. {
  4.     int child; // 孩子结点的下标（位置）
  5.     struct CTNode *next; 
  6. }*ChildPtr;
  8. // 这是顺序表的数据结构 
  9. typedef struct
  10. {
  11.     TElemType data;
  12.     ChildPtr firstchild;
  13. }CTBox;
  15. // 树的数据结构 
  16. typedef struct
  17. {
  18.     CTBox nodes[MAXSIZE];
  19.     int r,n; // 定义根的位置和结点数 
  20. }CTree;

这样定义的结构存在的问题是寻找双亲麻烦。

于是综合双亲表示法和孩子表示法，我们可以设计出双亲孩子表示法。
image.png

3.3 孩子兄弟表示法（从兄弟结点的角度看）

  1. 一棵树中，它的结点的第一个孩子唯一的（如果存在），且它的右兄弟也就是唯一的了（如果存在）。
  2. 这样设计的优势是把普通的树变成了二叉树（观察下面的大图）
  3. 左孩子，右孩子的兄弟

image.png（数据域，第一个孩子，右兄弟域）

比如，关于 3.1 中的示例图（6-4-1），我们可以如下表示
image.png
image.png

4. 树和森林的遍历（补充）

EL]D$_O6BPJTUY8RENS@M5D.png
image.png

4.1 树的先根遍历

image.png

4.2 树的后根遍历

image.png

4.3 森林的先序遍历

image.png

4.4 森林的中序遍历

image.png

4. 二叉树

  1. 二叉树由左，右子树组成，是有序树
  2. 适用于对某个结点都是两种结果的情形建模

4.1 二叉树的特点

  1. 每个结点最多两个子树
  2. 左子树和右子树有序。即使某结点只有一棵子树，也要区分左右
  3. 前序和后序遍历正好相反的二叉树，其高度等于结点数

PS：对于二叉树来说，由三个结点的二叉树会由五种情况（如下图），满足卡特琳公式
image.png

4.2 特殊的二叉树

1. 斜树

所有的结点都只有左子树（或者都只有右子树），就叫斜树

2. 满二叉树

所有的分支结点都存在左子树和右子树，并且叶子在同一层上。（我的理解是，这样的二叉树以根结点为轴左右对称）
image.png
特点：

  1. 只有最后一层有叶子结点
  2. 不存在度为 1 的结点

3. 完全二叉树

完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都从左至右按序填空依次排列

  1. 满二叉树是完全二叉树，但完全二叉树不一定是满二叉树

特点

  1. 叶子结点只可能在最下面两层
  2. 度为 1 的结点只可能有左孩子，且度为 1 的结点最多 1 个
  3. 同样结点数的二叉树，完全二叉树的深度最小
  4. 完全二叉树的排列是从左至右，中间不能跳
  5. i<=⌊n/2⌋为分支结点，i>⌊n/2⌋是叶子结点

举例

如下图中，树1，树2 和树3 不满足完全二叉树，树1：最下层的 11 结点并不是靠左对齐（即并不是左子树）。树2：到倒数第二层已经不是满二叉树了。树3：10 和 11 结点并不满足左靠的要求。
image.png
PS：同样的结点数，完全二叉树的深度最小
总结的比较好的链接

4.3 二叉树的性质

  1. 二叉树的第 i 层上至多有 2 个结点（用特殊值法去记忆）。
  2. 深度为 k 的二叉树最多有 2-1 个结点（用特殊值法去记忆）
  3. 终端结点个数 n 与 度为 2 的结点个数的关系，n = n + 1（如，仅有一个根结点，那么此时 n = 1，n = 0，二者满足 n = n + 1 的关系）
  4. 拥有 n 个结点的完全二叉树的深度为 第五章 树 - 图24，其中第五章 树 - 图25
  5. 具有 n 个结点的完全二叉树（其深度为 第五章 树 - 图26）的结点按层编号（i=1，2，3…）x
    1. i = 1，则结点 i 是二叉树的根；i > 1，则其双亲是结点，⌊i/2⌋
    2. 2i>n，则结点无左孩子；2i<=n，为左孩子
    3. 2i+1>n，则结点无右孩子；2i+1 <=n，为右孩子
  6. 给定 n 个结点可以构成的二叉树个数：第五章 树 - 图27（和出栈可能性的公式是一样的）
  7. 对于一个完全二叉树，如果给出结点数，可以推出度为 0，1，2 的结点的个数。就是利用上面的性质原理。

n1 = 0 or 1 ；n0 = n2+1
如，当完全二叉树的结点数为 2k 时，则要求度为 1 和度为 0，2的结点数之和为偶数，因为度为 0，2的结点数为奇数，所以必有度为1的结点数为 1。（具体见《天勤》P137）

note：

  1. 性质 1，2 分别对应等比数列的通项和等比数列前 n 项和。**在书中 P136**
  2. 性质 1，2 是结点最多的情况，就是满二叉树的情况

4.4 存储结构

1. 顺序结构

  1. 二叉树可以使用一维数组来实现顺序存储（如下图）
  2. 顺序存储结构一般只用于完全二叉树，因为消耗的空间太大了
  3. 不存在的结点用向上尖括号表示

image.png
image.png

可以看到，二叉树的存储是从 t[1] 开始的

2. 链式结构

孩子表示法
  1. 这种链表又叫二叉链表
  2. 包含了，数据域，左右孩子指针域
  1. typedef struct BiTNode
  2. {
  3.     TElemType data;
  4.     struct BiTNode *lchild,*rchild;
  5. }BiTNode,*BiTree;

image.png

二叉树的初始化
image.png

孩子兄弟表示法

image.png
image.png
note：

  1. 这里的右兄弟是指第一个孩子的右兄弟

4.5 遍历二叉树

  1. 定义：按某种次序（先序，中序，后序）依次访问二叉树中所有的结点，每个结点有且仅被访问一次

二叉树遍历的方法

推导遍历结果

应用：求树的深度

  1. int treeDepth(BiTree T)
  2. {
  3.     if(T==NULL) return 0;
  4.     else
  5.     {
  6.         int l = treeDepth(T->lchild);
  7.         int r = treeDepth(T->rchild);
  8.         return l>r?l+1;r+1;
  9.     }
  10. }

4.6 生成二叉树

二叉树的建立依赖于扩展二叉树。如下图，扩展二叉树是在一般的二叉树下（左侧），让每个叶子扩展出左右结点，这样做的目的是，在生成二叉树时，我们需要判断每个结点到哪里停止创建，而扩展的结点用 # 表示，也就是如果该结点是 # 的数值，那么就不生成这个结点。如，我们在键盘输入：AB#D#C# 为要创建的结点，在遇到 # 时就停止跳过不创建。
image.png。
二叉树的遍历利用的递归，同样二叉树的生成也是利用递归

// 生成二叉树
void CreateBiTree(BitTree *T)
{
    TElemType ch;
    scanf("%c",&ch);

    if(ch=="#")
        *T=NULL;
    else
    {
        *T=(BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(0);

        (*T)->data=ch; // 生成当前子树的根结点

        // 构造右子树 
        // (*T)->lchild 表示指向右子树
        // &(*T)->lchild 因为下一次的操作是生成新的右子树
        // 用 & 返回地址 
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

4.7 线索二叉树

  1. 作用：充分利用下图中，空指针区域（空着就是在浪费啊）
  2. 空指针域的个数：2n-(n-1)=n+1
  3. 如何利用：存放该结点的前驱和后继（指向前驱和后继的指针就叫做线索）

第五章 树 - 图35

  1. 如，中序遍历中，将空的右结点改为指向该结点的后继，空的左结点改为指向该结点的前驱（反过来也可以）

  2. 判断左右指针是指向前驱（后继）还 是左孩子（右孩子）：设置两个标志位。为 0 表示指向孩子，反之为前驱后继

image.png

  1. 线索二叉树结构与实现

线索化本质就是将二叉链表中的空指针改为指向前驱或者后继的线索，线索化的过程就是在遍历的过程中修改空指针的过程

结点数据结构

typedef struct TBTNode
{
    char data;
    // 相当于只比二叉树的结点结构多了两个标志位
    int ltag,rtag;
    struct TBTNode *lchild;
    struct TBTNode *rchild;
}TBTNode;

中序遍历**对二叉树线索化**

image.png

中序线索二叉树中找中序后继

核心思想：如果 p 指向的结点直接指向后继，即 p->rtag=1，那么下一个就是后继。如果 p->rtag =0，说明当前结点的下一个结点是孩子，而非后继，则要找后继，只需要将 p 的右子树，进行左查找，即一直找到右子树的最左边的结点，就是中序遍历中的 p 的下一个后继。（前驱亦是如此）。
image.png
中序线索二叉树中找前驱
image.png

note：

  1. 线索二叉树的前驱与后继是按中序遍历，结点 X 前后的两个结点。

    5. 树，森林与二叉树的转换

    借助二叉链表，可以把树和二叉树进行转换。二叉链表的核心思想就是结点 A 所链接的是第一个孩子，这个孩子的右兄弟

  2. 转换成二叉树都是添加横线，去除上下线

5.1 树转换成二叉树

步骤

  1. 兄弟加线
  2. 非长子去线
  3. 调整层次，长子在左。兄弟在右

二叉树转换成树，就是把其当作孩子兄弟表示法，左边是孩子，右边是兄弟。 反之一样
image.png

5.2 森林转换为二叉树

步骤

  1. 把每棵树转换为二叉树
  2. 右树木依次变右孩子

image.png

5.3 二叉树转换成树

步骤

  1. 加线。所有左孩子的右结点都归为上一层级的孩子
  2. 删除所有结点与右孩子的连线
  3. 调整层次

image.png

5.4 二叉树转换成森林

步骤

  1. 将二叉树的右孩子递归剥离出去
  2. 采用二叉树转换成树的方法即可

image.png

6. 哈夫曼树

哈夫曼树用于最基本的压缩编码（如，.zip 压缩文件）中，也叫哈夫曼编码

6.1 哈夫曼树定义及其原理

定义

  1. 路径：从一个结点到另一个结点经过的分支（从上往下），也就是边的数量
  2. 路径长度：路径上分支的数目
  3. 树的路径长度：从树根到每个结点的路径长度之和
  4. 带权路径长度：从该结点到树根之间的路径长度（结点所在层数，从0开始）与结点上的权的乘积
  5. 树的带权路径长度：树中叶子结点带权路径长度之和

image.png（note：根节点层数为 0）

  1. 哈夫曼树：带权路径长度 WPL 最小的二叉树（最优二叉树）。它的特点是带权路径最短。

特点

  1. 权值越大，距离树根越近
  2. 正则（严格）二叉树：每个非叶结点都有左右子树

实例

image.png

  1. 根结点和 A 结点的路径长度：3
  2. 树的路径长度：1+2+2+1+2+2+3+3 = 16
  3. 树的带权路径长度：53+153+402+302+102 = 220（叶结点的值所在层数）

构造哈夫曼树（冒泡构造法）

image.png

  1. 权值按从小到达排序
  2. 选取最小的两个开始作为左右结点（小的作为左结点，大的作为右结点）
  3. 将上述结点生成一个新根（根的权值是两个孩子的权值之和），与下一个结点的权值按步骤 2 比较
  4. 以同样的方式继续构造，直到结束

重要：哈夫曼树的特性就是产生的带权路径长度最短

实例

假设六个字母的频率（字符出现的次数）为 A 27 , B 8, C 15 , D 15 , E 30, F 5

构造的哈夫曼树
image.png

同一组结点，哈夫曼树构造的结果可能是不一样的，但是其 wpl 是一样

7. 哈夫曼编码

PS：这一小节写的不详细，具体可以参考《大话数据结构》或者 google
作用：解决长距离数据传输中的优化问题

接上一节的图，我们已经构造出了哈夫曼树，将分支的权值换成 0 ，1，得到下图
image.png
此时我们对其进行编码，可以得到下表，和原码比较数据被压缩了（规定左分支代表 0 ，右分支代表 1）
比如，B（1001）表示 B 结点到根结点路径的权值是 1，0，0，1
image.png

解码的方式也是采用哈夫曼树的构造

note

  1. 哈夫曼编码中任何一个序列都不是其他序列的前缀，如，绝不可能出现有 100，10这样的编码，因为 10 是 100 的前缀。在图形上的表示即是，所有的有效结点（被编码的结点）都在叶子上（如上图），不可能出现在途径中

  2. 哈夫曼树没有单分支节点


    哈夫曼编码的疑问
    因为哈夫曼编码采用的是前缀码，所以解码的时候不会出现解码歧义。如下图

image.png