【数据结构】第五章：树与二叉树

本篇笔记课程来源：王道计算机考研 数据结构

一、树的定义

1. 基本概念

• 树是 n（n≥0）个结点的有限集合，n = 0 时，称为空树，这是一种特殊情况。在任意一颗非空树中应满足：
  1. 有且仅有一个特定的称为根的结点。
  2. 当 n > 1 时，其余结点可分为 m（m>0）个互不相交的有限集合 $T_1,T_2,...,T_m$，其中每个集合本身又是一棵树，并且称为根节点的子树。
• 非空树的特性：
  1. 有且只有一个根节点
  2. 没有后继的结点称为 “叶子结点”（或终端结点）
  3. 有后继的结点称为 “分支节点”（或非终端结点）
  4. 除了根节点外，任何一个结点都有且仅有一个前驱
  5. 每个结点可以有 0 个或多个后继

2. 基本术语

• 结点之间的关系描述：祖先结点和子孙结点、父结点（双亲结点）和子结点、兄弟结点和堂兄弟结点；
• 结点之间的路径：经过了哪些结点（只能从上往下）；
• 结点之间的路径长度：路径上经过多少条边；
• 结点的层次（深度）：从上往下数第几层（默认从 1 开始）；
• 结点的高度：从下往上数第几层；
• 树的高度（深度）：总共多少层；
• 结点的度：该结点有几个分支；
  • 非叶子结点的度 > 0
  • 叶子结点的度 = 0
• 树的度：各结点的度的最大值；
• 有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换；
• 无序树：逻辑上看，树中结点的各子树从左至右是无次序的，可以互换；
• 森林：是 m（m≥0）颗互不相交的树的集合。

3. 常见性质

• 结点数 = 总度数 + 1

• 度为 m 的树和 m 叉树

  度为 m 的树	m 叉树
  数的度 —— 各结点的度的最大值	每个结点最多只能有 m 个孩子的树
  任意结点的度 ≤ m（最多 m 个孩子）	任意结点的度 ≤ m（最多 m 个孩子）
  至少有一个结点度 = m（有 m 个孩子）	允许所有结点的度都 ≤ m
  一定是非空树，至少有 m+1 个结点	可以是空树

• 度为 m 的树和 m 叉树第 i 层至多有 $m^{i-1}$ 个结点（i≥1）

• 高度为 h 的 m 叉树至多有 $\frac{m^h-1}{m-1}$ 个结点

• 高度为 h 的 m 叉树至少有 h 个结点，高度为 h，度为 m 的树至少有 $h+m-1$ 个结点

• 具有 n 个结点的 m 叉树的最小高度为 $\lceil lo{g}_m(n(m-1)+1)\rceil$

二、二叉树的定义

1. 基本概念

• 二叉树是 n（n ≥ 0）个结点的有限集合：
  1. 或者为空二叉树，即 n = 0
  2. 或者由一个根节点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。
• 特点：
  1. 每个结点至多只有两颗子树
  2. 左右子树不能颠倒（二叉树是有序树）
• 二叉树的五种状态：
  1. 空二叉树
  2. 只有左子树
  3. 只有右子树
  4. 只有根节点
  5. 左右子树都有

2. 特殊二叉树

• 满二叉树：除了叶子结点以外的每个结点都有两个分支。
  
  一颗高度为 h，且含有 $2^h-1$ 个结点的二叉树特点：
  1. 只有最后一层有叶子结点
  2. 不存在度为 1 的结点
  3. 按层序从 1 开始编号，结点 i 的左结点为 $2i$，右结点为 $2i+1$；结点 i 的父结点为 $\lfloor i/2\rfloor$（如果有的话）
• 完全二叉树：当且仅当其每个结点都与高度为 h 的满二叉树中编号 1~n 的结点一一对应时，称为完全二叉树。
  
  特点：
  1. 只有最后两层可能有叶子结点
  2. 最多只有一个度为 1 的结点
  3. 按层序从 1 开始编号，结点 i 的左结点为 $2i$，右结点为 $2i+1$；结点 i 的父结点为 $\lfloor i/2\rfloor$（如果有的话）
  4. $i\le \lfloor n/2\rfloor$ 为分支结点，$i>\lfloor n/2\rfloor$ 为叶子结点（$i$ 为当前结点编号，$n$ 为总共有多少结点）
• 二叉排序树：用于元素的排序和搜索。
  
  特点：
  1. 左子树上所有结点的关键字均小于根节点的关键字
  2. 右子树上所有结点的关键字均大于根节点的关键字
  3. 左子树和右子树又各是一颗二叉排序树
• 平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过 1。
  

3. 常见性质

• 二叉树：
  1. 设非空二叉树中度为 0、1、2 的结点个数分别为 $n_0、n_1、n_2$，则 $n_0=n_2+1$（叶子结点比二分支结点多一个）
  2. 二叉树第 i 层最多有 $2^{i-1}$ 个结点（i≥1）
  3. 高度为 h 的二叉树最多有 $2^h-1$ 个结点（满二叉树）
• 完全二叉树：
  1. 第 i 个结点所在层次 和 具有 n 个（n>0）结点的完全二叉树的高度 h 都为 $\lceil lo{g}_2(n+1)\rceil$ 或 $\lfloor lo{g}_{2}n\rfloor +1$
  2. 可以由结点数 n 推出度为 0、1、2 的结点个数 $n_0、n_1、n_2$：
     若完全二叉树有 2k（偶数）个结点，则必有 $n_1=1，n_0=k，n_2=k-1$；
     若完全二叉树有 2k-1（奇数）个结点，则必有 $n_1=0，n_0=k，n_2=k-1$。

三、二叉树的存储结构

1. 顺序存储

• 二叉树的顺序存储结构，只适合存储完全二叉树，且一定要把二叉树的节点编号和完全二叉树对应起来。

  #define MaxSize 100
  
  // 让第一个为止空缺，保证数组下标和结点编号一直，因此能存储 MaxSize-1 个结点
  struct TreeNode {
      int value;      // 节点中的数据元素
      bool isEmpty;   // 结点是否为空
  };
  
  // 定义一个数组存储二叉树中的结点
  TreeNode t[MaxSize];
  
  // 初始化时所有结点标记为空
  void InitTree(TreeNode * t) {
      for (int i = 0; i < MaxSize; i++) {
          t[i].isEmpty = true;
      }
  }
  

• 基本操作：
  1. i 结点的左结点 —— $2i$
  2. i 结点的右节点 —— $2i+1$
  3. i 结点的父结点 —— $\lfloor i/2\rfloor$
  4. i 结点所在的层次 —— $\lceil lo{g}_2(i+1)\rceil$ 或 $\lfloor lo{g}_{2}i\rfloor +1$

• 若完全二叉树中共有 n 个结点，则：
  • 判断 i 结点是否有左孩子 —— $2i\le n$
  • 判断 i 结点是否有右孩子 —— $2i+1\le n$
  • 判断 i 结点是否有叶子 / 分支结点 —— $i>\lfloor n/2\rfloor$

2. 链式存储

• 实现

  typedef struct BiTNode {
      int data;       // 数据域
      struct BiTNode *lchild, *rchild;    // 左右孩子指针
  } BiTNode, *BiTree;
  
  // 插入根结点
  bool InsertRootNode(BiTree *T) {
      BiTree root = (BiTree)malloc(sizeof(BiTree));
      if (T == NULL) return false;
      root->data = 1;
      root->lchild = root->rchild = NULL;
      return true;
  }
  
  // 插入左结点
  bool InsertLeftBiTNode(BiTNode *T, int data) {
      BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
      if (p == NULL) return false;
      p->data = data;
      p->lchild = p->rchild = NULL;
      T->lchild = p;
      return true;
  }
  

• 性质：n 个结点的二叉链表共有 n+1 个空链域
• 如果需要频繁搜索父结点可使用三叉链表

四、二叉树的遍历

• 二叉树的递归特性：
  1. 要么是个空树
  2. 要么就是由 “根结点 + 左子树 + 右子树” 组成的二叉树

1. 先序遍历

• 也叫先根遍历（PreOrder），遍历顺序为：根左右（NLR）

• 操作过程：
  1. 若二叉树为空，则什么都不做
  2. 若二叉树非空：
     1. 访问根结点
     2. 先序遍历左子树
     3. 先序遍历右子树

• 实现：第一次路过时访问

  void PreOrder(BiTree T){
  	if (T != NULL){
  		visit(T);				// 访问根结点
  		PreOrder(T->lchild);	// 递归遍历左子树
  		PreOrder(T->rchild);	// 递归遍历右子树
  	}
  }
  

2. 中序遍历

• 也叫中根遍历（InOrder），遍历顺序为：左根右（LNR）

• 操作过程：
  1. 若二叉树为空，则什么都不做
  2. 若二叉树非空：
     1. 中序遍历左子树
     2. 访问根结点
     3. 中序遍历右子树

• 实现：第二次路过时访问

  void InOrder(BiTree T){
  	if (T != NULL){
  		InOrder(T->lchild);	// 递归遍历左子树
  		visit(T);			// 访问根结点
  		InOrder(T->rchild);	// 递归遍历右子树
  	}
  }
  

3. 后序遍历

• 也叫后根遍历（PostOrder），遍历顺序为：左右根（LRN）

• 操作过程：
  1. 若二叉树为空，则什么都不做
  2. 若二叉树非空：
     1. 后序遍历左子树
     2. 后序遍历右子树
     3. 访问根结点

• 实现：第三次路过时访问

  void PostOrder(BiTree T){
  	if (T != NULL){
  		PostOrder(T->lchild);	// 递归遍历左子树
  		PostOrder(T->rchild);	// 递归遍历右子树
  		visit(T);				// 访问根结点
  	}
  }
  

• 求树的深度

  int TreeDepth(Bitree T){
  	if (T == NULL) return 0;
  	else {
  		int l = TreeDepth(T->lchild);
  		int r = TreeDepth(T->rchild);
  		// 树的深度=Max(左子树深度, 右子树深度)+1
  		return l > r ? l + 1 : r + 1;
  	}
  }
  

4. 层序遍历

• 层序遍历（LevelOrder）算法思想：
  1. 初始化一个辅助队列
  2. 根结点入队
  3. 若队列非空，则队头结点出队，访问该结点，并将其左、右结点插入队尾（如果有的话）
  4. 重复第三步，直到队列为空
• 实现

  typedef struct BiTNode{
  	int data;
  	struct BitNode *lchild, *rchild;
  } BiTNode, *BiTree;
  
  typedef struct LinkNode{
  	BiTNode * data;
  	LinkNode *front, *rear;
  } LinkNode, *LinkQueue;
  
  void LevelOrder(BiTree T){
  	LinkQueue Q;
  	InitQueue(Q);			// 初始化辅助队列
  	BiTree P;
  	EnQueue(Q, T);			// 根结点入队
  	while (!IsEmpty(Q)){	// 队列不空则循环
  		DeQueue(Q, p);		// 队头结点出队
  		visit(p);			// 访问出队结点
  		if (p->lchild != NULL)
  			EnQueue(Q, p->lchild);	// 左结点入队
  		if (p->rchild != NULL)
  			EnQueue(Q, p->rchild);	// 右结点入队
  	}
  }
  

5. 由遍历序列构造二叉树

• 若只给出一颗二叉树的前、中、后、层序序列的一种，不能唯一确定一棵二叉树。
• 前序、后序、层序序列的两两组合，不能唯一确定一颗二叉树。
• 若给出中序序列和其他任意一种序列，可以唯一确定一颗二叉树：
  1. 前序 + 中序
  2. 后序 + 中序
  3. 层序 + 中序
• 首先找到树的根结点，并根据中序序列划分左右子树，再找到左右子树根结点。

五、线索二叉树

1. 基本概念

• n 个结点的二叉树，有 n+1 个空链域，这些空链域可用来记录前驱、后继的信息

• 指向前驱、后继的指针称为 “线索”，分别为：前驱线索、后继线索

• 作用：方便从一个指定结点出发，找到其前驱、后继；方便遍历

• 实现：
  tag 为 0 时，表示指针指向子结点；
  tag 为 1 时，表示指针是 “线索”。

  typedef struct ThreadNode {
  	int data;
  	ThreadNode *lchild, *rchild;
  	int ltag, rtag;		// 左、右线索标志
  }
  

2. 三种线索二叉树

• 中序线索二叉树：以中序遍历序列为依据进行线索化，线索指向中序前驱、中序后继
  
• 先序线索二叉树：以先序遍历序列为依据进行线索化，线索指向先序前驱、先序后继
  
• 后序线索二叉树：以后序遍历序列为依据进行线索化，线索指向后序前驱、后序后继
  

3. 二叉树的线索化

• 算法核心：是对遍历算法的改造，用一个指针 pre 记录当前访问节点的前驱结点，当访问一个结点时，连接该结点与前驱节点的线索信息。
• 注意最后一个结点的 rchild、rtag 的处理
• 中序线索化

  // 定义线索二叉树结点
  typedef struct ThreadNode{
  	int data;
  	ThreadNode *lchild, *rchild;
  	int ltag, rtag;		// 左、右线索标志
  } ThreadNode, *ThreadTree;
  
  // 定义全局变量 pre，指向当前访问结点的前驱
  ThreadNode *pre = NULL;
  
  // 中序线索化二叉树 T
  void CreateInThread(ThreadTree T){
  	pre = NULL;				// pre 初始为 NULL
  	if (T != NULL){			// 非空二叉树才能线索化
  		InThread(T);		// 中序线索化二叉树
  		if (pre->rchild == NULL)
  			pre->rtag = 1;	// 处理遍历的最后一个结点
  	}
  }
  
  // 改造中序遍历算法，一边遍历一边线索化
  void InThread(ThreadTree T){
  	if (T != NULL){
  		InThread(T->lchild);	// 中序遍历左子树
  		Visit(T);				// 访问根结点
  		InThread(T->rchild);	// 中序遍历右子树
  	}
  }
  
  void Visit(ThreadNode *q){
  	// 左子树为空，建立前驱线索
  	if (q->lchild == NULL){
  		q->lchild = pre;
  		q->ltag = 1;
  	}
  	// 建立前驱节点的后继线索
  	if (pre != NULL && pre->rchild == NULL){
  		pre->rchild = q;
  		pre->rtag = 1;
  	}
  	pre = q;
  }
  

• 先序线索化：注意处理死循环问题，当 ltag == 0 时，才能对左子树先序线索化。

  // 定义线索二叉树结点
  typedef struct ThreadNode{
  	int data;
  	ThreadNode *lchild, *rchild;
  	int ltag, rtag;		// 左、右线索标志
  } ThreadNode, *ThreadTree;
  
  // 定义全局变量 pre，指向当前访问结点的前驱
  ThreadNode *pre = NULL;
  
  // 先序线索化二叉树 T
  void CreatePreThread(ThreadTree T){
  	pre = NULL;				// pre 初始为 NULL
  	if (T != NULL){			// 非空二叉树才能线索化
  		PreThread(T);		// 先序线索化二叉树
  		if (pre->rchild == NULL)
  			pre->rtag = 1;	// 处理遍历的最后一个结点
  	}
  }
  
  // 改造先序遍历算法，一边遍历一边线索化
  void PreThread(ThreadTree T){
  	if (T != NULL){
  		Visit(T);				// 先访问根结点
  		if (T->ltag == 0)		// lchild 不是前驱线索
  			PreThread(T->lchild);
  		PreThread(T->rchild);
  	}
  }
  
  void Visit(ThreadNode *q){
  	// 左子树为空，建立前驱线索
  	if (q->lchild == NULL){
  		q->lchild = pre;
  		q->ltag = 1;
  	}
  	// 建立前驱节点的后继线索
  	if (pre != NULL && pre->rchild == NULL){
  		pre->rchild = q;
  		pre->rtag = 1;
  	}
  	pre = q;
  }
  

• 后序线索化

  ...重复代码省略...
  
  // 改造后序遍历算法，一边遍历一边线索化
  void PostThread(ThreadTree T){
  	if (T != NULL){
  		PostThread(T->lchild);
  		PostThread(T->rchild);
  		Visit(T);
  	}
  }
  
  ...重复代码省略...
  

4. 中序线索二叉树找前驱 / 后继

• 中序找后继，两种情况：
  1. 若 p->rtag == 1，则 next = p->rchild
  2. 若 p->rtag == 0，则 next 为 p 的右子树中最左下结点（往右走一步，往左走到底）

  // 找到以 P 为根的子树中，第一个被中序遍历的结点
  ThreadNode *FirstNode(ThreadNode *p){
  	// 循环找到最左下结点（不一定是叶子结点）
  	while (p->ltag == 0)
  		p = p->lchild;
  	return p;
  }
  
  // 在中序线索二叉树中找到结点 p 的后继结点
  ThreadNode *NextNode(ThreadNode *p){
  	// 右子树中最左下结点
  	if (p->rtag == 0)
  		return FirstNode(p->rchild);
  	else
  		return p->rchild;	// rtag == 1 直接返回后继线索
  }
  
  // 对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
  void InOrder(ThreadNode *T){
  	for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p))
  		Visit(p);
  }
  

• 中序找前驱，两种情况：
  1. 若 p->ltag == 1，则 pre = p->lchild
  2. 若 p->ltag == 0，则 pre 为 p 的左子树中最右下结点（往左走一步，往右走到底）

  // 找到以 P 为根的子树中，最后一个被中序遍历的结点
  ThreadNode *LastNode(ThreadNode *p){
  	// 循环找到最右下结点（不一定是叶子结点）
  	while (p->rtag == 0)
  		p = p->rchild;
  	return p;
  }
  
  // 在中序线索二叉树中找到结点 p 的前驱结点
  ThreadNode *PreNode(ThreadNode *p){
  	// 左子树中最右下结点
  	if (p->ltag == 0)
  		return LastNode(p->lchild);
  	else
  		return p->lchild;	// ltag == 1 直接返回前驱线索
  }
  
  // 对中序线索二叉树进行逆向中序遍历
  void RevInOrder(ThreadNode *T){
  	for (ThreadNode *p = LastNode(T); p != NULL; p = PreNode(p))
  		Visit(p);
  }
  

5. 先序线索二叉树找前驱 / 后继

• 先序找后继，两种情况：
  1. 若 p->rtag == 1，则 next = p->rchild
  2. 若 p->rtag == 0，则又分为两种情况：
     1. 若 p 有左结点，则先序后继为左结点
     2. 若 p 没有左结点，则先序后继为右结点

  // 在先序线索二叉树中找到结点 p 的后继结点
  ThreadNode *NextNode(ThreadNode *p){
  	if (p->rtag == 0)
  		return p->ltag == 0 ? p->lchild : p->rchild;
  	else
  		return p->rchild;	// rtag == 1 直接返回后继线索
  }
  
  // 对先序线索二叉树进行先序遍历
  void PreOrder(ThreadNode *T){
  	for (ThreadNode *p = T; p != NULL; p = NextNode(p))
  		Visit(p);
  }
  

• 先序找前驱，需使用三叉链表，两种情况
  1. 若 p->ltag == 1，则 pre = p->lchild
  2. 若 p->ltag == 0，则又分为四种情况：
     1. 若能找到 p 的父结点，且 p 为父结点的左结点，则 p 的父结点为其前驱
     2. 若能找到 p 的父结点，且 p 为父结点的右节点（左结点为空），则 p 的父结点为其前驱
     3. 若能找到 p 的父结点，且 p 为父结点的右节点（左结点非空），则 p 的前驱为左兄弟子树中最后一个被先序遍历的结点（优先往右走）
     4. 若 p 为根结点，则 p 没有先序前驱

6. 后序线索二叉树找前驱 / 后继

• 后序找前驱（类似于先序找后继），两种情况：
  1. 若 p->ltag == 1，则 pre = lchild
  2. 若 p->ltag == 0，则又分为两种情况：
     1. 若 p 有右结点，则后序前驱为右结点
     2. 若 p 没有右结点，则后序前驱为左结点
• 后序找后继（类似于先序找前驱），需使用三叉链表，两种情况：
  1. 若 p->rtag == 1，则 next = rchild
  2. 若 p->rtag == 0，则又分为四种情况：
     1. 若能找到 p 的父结点，且 p 为父结点的右结点，则 p 的父结点为其后继
     2. 若能找到 p 的父结点，且 p 为父结点的左结点（右结点为空），则 p 的父结点为其后继
     3. 若能找到 p 的父结点，且 p 为父结点的左结点（右结点非空），则 p 的后继为右兄弟子树中第一个被后序遍历的结点（优先往左走）
     4. 若 p 为根结点，则 p 没有后序后继

六、树的存储结构

1. 顺序存储

• 顺序存储，也叫双亲表示法，每个结点中保存指向父结点的数组索引号。
• 根结点固定存储在 0，-1 表示没有父结点。

#define MAX_TREE_SIZE 100   // 树中最多结点数

typedef struct {            // 树的结点定义
    int data;               // 数据元素
    int parent;             // 父结点位置域
} PTNode;

typedef struct {                    // 树的类型定义
    PTNode nodes[MAX_TREE_SIZE];    // 双亲表示法
    int n;                          // 结点数
} PTree;

• 添加结点：无需按逻辑上的次序存储，直接插入进数组。
• 删除结点：
  1. 如果是叶子结点，删除结点后将数组中最后一个结点数据放到删除结点所在的位置。
  2. 如果是分支结点，删除结点子树中所有的结点。
• 优点：查指定结点的父结点很方便。
• 缺点：差指定结点的子结点只能从头遍历。

2. 顺序 + 链式存储

• 也叫孩子表示法，顺序存储各个结点，每个结点中保存孩子链表头指针。

#define MAX_TREE_SIZE 100

// 定义孩子结点链表
struct CTNode {
    int child;      // 孩子结点在数组中的位置
    CTNode *next;   // 下一个孩子
};

// 定义结点
typedef struct {
    int data;               // 数据元素
    CTNode *first_child;    // 第一个孩子
} CTBox;

// 顺序存储所有结点
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;       // 结点数 和 根的位置
} CTree;

3. 链式存储

• 也叫孩子兄弟表示法，用纯链式的方式存储一棵树。
• 用二叉链表存储树：左孩子右兄弟

// 链式存储，类似于二叉链表
typedef struct CSNode {
    int data;                               // 数据域
    CSNode *first_child, *next_sibling;     // 第一个孩子和右兄弟指针
} CSNode, *CSTree;

• 优点：可以实现树和二叉树的转换，可以用二叉树操作来处理树。
  

七、树和森林的遍历

1. 树的遍历

• 先根遍历：若树非空，先访问根结点，再依次对每颗子树进行先根遍历。
  树的先根遍历序列与这棵树相应二叉树的先序序列相同。

  // 树的先根遍历
  void PreOrder(TreeNode *R){
  	if (R != NULL){
  		visit(R);			// 访问根结点
  		while(R还有下一个子树T)
  			PreOrder(T);	// 先根遍历下一颗子树	
  	}
  }
  

• 后根遍历：若树非空，先依次对每颗子树进行后根遍历，最后再访问根结点。
  树的后根遍历序列与这棵树相应二叉树的中序序列相同。

  // 树的后根遍历
  void PostOrder(TreeNode *R){
  	if (R != NULL){
  		while(R还有下一个子树T)
  			PostOrder(T);	// 后根遍历下一颗子树
  		visit(R);			// 访问根结点
  	}
  }
  

• 层序遍历（用队列实现）：

  1. 若树非空，则根结点入队
  2. 若队列非空，队头元素出队并访问，同时将该元素的子结点依次入队
  3. 重复 2 直到队列为空

2. 森林的遍历

• 先序遍历，效果等同于依次对各个树进行先根遍历：
  1. 若森林非空，则访问森林中第一棵树的根结点。
  2. 先序遍历第一棵树中根结点的子树森林。
  3. 先序遍历除去第一棵树之后剩余的树构成的森林。

• 中序遍历，效果等同于依次对各个树进行后根遍历：
  1. 若森林非空，则中序遍历森林中第一棵树的根结点的子树森林。
  2. 访问第一棵树的根结点。
  3. 中序遍历除去第一棵树之后剩余的树构成的森林。

3. 遍历方式对比

• 同一排的遍历方式可互相转换

  树	森林	二叉树
  先根遍历	先序遍历	先序遍历
  后根遍历	中序遍历	中序遍历

八、哈夫曼树

1. 哈夫曼树的定义

• 结点的权：有某种现实含义的数值（如：表示结点的重要性等）

• 结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积

• 树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL，Weighted Path Length）$$WPL=\sum _{i=1}^n{w}_i{l}_i$$

• 哈夫曼树：也称最优二叉树，在含有 n 个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树。

2. 哈夫曼树的构造

• 给定 n 个权值分别为 $w_1,w_2,...,w_n$ 的结点，构造哈夫曼树的算法描述如下：
  1. 将这 n 个结点分别作为 n 颗仅含一个结点的二叉树，构成森林 F；
  2. 构造一个新节点，从 F 中选取两颗根结点权值最小的树作为新节点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和；
  3. 从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中；
  4. 重复步骤 ② 和 ③，直至 F 中只剩下一棵树为止。

• 构造哈夫曼树的特点：
  1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
  2. 哈夫曼树的结点总数为 $2n-1$
  3. 哈夫曼树中不存在度为 1 的结点
  4. 哈夫曼树并不唯一，但 WPL 必然相同且为最优

3. 哈夫曼编码

• 固定长度编码：每个字符用相等长度的二进制位表示（如 ASCII 码）
• 可变长度编码：允许对不同字符用不等长的二进制位表示（如 哈夫曼编码）
• 前缀编码：若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码（前缀编码解码无歧义）
• 哈夫曼编码：由哈夫曼树得到，字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据构造算法构造哈夫曼树，即可得到哈夫曼编码，可用于数据压缩（哈夫曼树不唯一，因此哈夫曼编码也不唯一）

九、并查集

1. 逻辑结构

• 并查集，逻辑上是将各个元素划分为若干个互不相交的子集。
• 因此，本质上是集合的逻辑结构。
  

2. 存储结构

• 适合采用树的顺序存储（双亲表示法）：每个结点中保存指向父结点的数组索引号。

  #define MAX_TREE_SIZE 100			// 树中最多结点数
  
  typedef struct {					// 树的结点定义
  	ELemType data;					// 数据元素
  	int parent;						// 父结点位置域
  } PTNode;
  
  typedef struct {					// 树的类型定义（顺序存储）
  	PTNode nodes[MAX_TREE_SIZE];	// 双亲表示法
  	int n;							// 结点数
  } PTree;
  

3. 基本操作

• 初始化：初始化并查集，将所有数组元素初始化为 -1

  void Initial(PTree &T){
  	for (int i = 0; i < T.n; i++)
  		T.nodes[i] = -1;
  }
  

• 查：确定一个指定元素 x 所属集合，最坏时间复杂度 O(n)

  // Find 查操作，找到下标为 x 的元素所属集合（返回 x 所属根结点）
  int Find(PTree &T, int x){
  	while (T.nodes[x] >= 0)		// 循环寻找根结点
  		x = T.nodes[x];
  	return x;					// 根的父节点位置域小于 0
  }
  

• 并：将两个不相交的集合合并为一个集合，时间复杂度 O(1)。将 n 个独立元素通过多次 Union 合并为一个集合的时间复杂度为 $O(n^2)$

  // Union 并操作，将两个集合合并为一个
  void Union(PTree &T, int root_1, int root_2){
  	// 要求 root_1 和 root_2 是不同的集合
  	if (root_1 == root_2) return;
  	// 将根 root_2 连接到另一根 root_1 下面
  	T.nodes[root_2] = root_1;
  }
  

4. 优化 “并” 操作

• 优化思路：在每次 Union 操作构建树时，尽可能让树不长高
  1. 用根结点的绝对值表示树的结点总数（如 -6 表示有 6 个结点）
  2. Union 操作，让小树合并到大树

// Union 并操作，小树合并到大树
void Union(PTree &T, int root_1, int root_2){
	if (root_1 == root_2) return;
	if (T.nodes[root_2] > T.nodes[root_1]) {	// root_2 结点数更少
		T.nodes[root_1] += T.nodes[root_2];		// 累加结点总数
		T.nodes[root_2] = root_1;				// 小树合并到大树
	}else{
		T.nodes[root_2] += T.nodes[root_1];		// 累加结点总数
		T.nodes[root_1] = root_2;				// 小树合并到大树
	}
}

• 该方法构造的树高不超过 $\lfloor lo{g}_{2}n\rfloor +1$，Find 查操作最坏时间复杂度变为 $O(lo{g}_{2}n)$，将 n 个独立元素通过多次 Union 合并为一个集合的时间复杂度为 $O(nlo{g}_{2}n)$

5. 优化 “查” 操作

• 核心思想：压缩路径，尽可能让树变矮。
• 压缩路径：Find 操作，先找到根结点，再将查找路径上所有结点都挂到根结点下。

// Find 查操作优化，先找到根结点，再进行 压缩路径
int Find(PTree &T, int x){
	int root = x;
	while (T.nodes[root] >= 0)
		root = T.nodes[root];	// 循环找到根
	while (x != root){			// 压缩路径
		int temp = T.nodes[x];	// temp 指向 x 的父结点
		T.nodes[x] = root;		// x 直接挂到根结点下
		x = temp;
	}
	return root;				// 返回根结点编号
}

• 设 $\alpha (n)$ 是一个增长很缓慢的函数，对于常见的 $n$ 值，通常 $\alpha (n)\le 4$。
• 优化查操作后，树的高度不超过 $\alpha (n)$，时间复杂度 $O(\alpha (n))$，将 n 个独立元素通过多次 Union 合并为一个集合的时间复杂度为 $O(n\alpha (n))$