当前位置：首页 > news >正文

【学习笔记】数据结构（六 ②）

news 来源：原创 2024/9/20 15:06:32

树和二叉树（二）

文章目录

树和二叉树（二）
- - 6.3.2 线索二叉树
- 6.4 树和森林
- - 6.4.1 树的存储结构
  - 6.4.2 森林与二叉树的转换
  - 6.4.3 树和森林的遍历
- 6.5 树与等价问题
- - 6.5.1 等价定义
  - 6.5.2 划分等价类的方法
  - 6.5.3 划分等价类的具体操作 - 并查集MFSet
  - 6.5.4 用树型结构表示集合
  - 6.5.5 并查集及其优化
- 6.6 赫夫曼树及其应用
- - 6.6.1 最优二叉树(赫夫曼树)
  - 6.6.2 赫夫曼编码
- 6.7 回溯法与树的遍历
- 6.8 树的计数

6.3.2 线索二叉树

lchild	LTag	data	RTag	rchild

LTag = 0 lchild 域指示结点的左孩子
LTag = 1 lchild 域指示结点的前驱
RTag = 0 rchild域指示结点的右孩子
RTag= 1 rchild域指示结点的后继

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树 (Threaded Binary Tree) 。

对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

#define TElemType char//宏定义，结点中数据域的类型
//枚举，Link（孩子）为0，Thread（线索）为1
typedef enum {Link,Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode {TElemType data;//数据域struct BiThrNode* lchild, * rchild;//左孩子，右孩子指针域PointerTag LTag, RTag;//标志域，枚举类型
}BiThrNode, * BiThrTree;

在这里插入图片描述

先序线索化

/*  先序线索化  */
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>#define TElemType char//宏定义，结点中数据域的类型
//枚举，Link为0，Thread为1
typedef enum {Link,Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode {TElemType data;//数据域struct BiThrNode* lchild, * rchild;//左孩子，右孩子指针域PointerTag LTag, RTag;//标志域，枚举类型
}BiThrNode, * BiThrTree;//创建二叉树
BiThrTree CreateBiTree();
//创建线索二叉树
void CreatePreThread(BiThrTree T);
//先序遍历线索化
void PreThread(BiThrTree T);
void Visit(BiThrNode* q);//后继
BiThrNode* NextNode(BiThrNode* p);
//对先序线索二叉树进行先序遍历
void PrintElement(TElemType e);
void PreOrder(BiThrTree T);BiThrNode* pre = NULL;int main() {BiThrTree T = NULL;printf("输入前序二叉树:\n");  // abd#g##e##cf###T = CreateBiTree();CreatePreThread(T);PreOrder(T);return 0;
}//先序创建二叉树
BiThrTree CreateBiTree() {char ch;if (scanf(" %c", &ch) != 1) { // 检查输入是否成功// 输入失败，可能是文件结束符或错误输入exit(EXIT_FAILURE);}if (ch != '#') {BiThrNode* node = (BiThrNode*)malloc(sizeof(BiThrNode)); // 分配内存if (node == NULL) {// 内存分配失败perror("内存分配失败");exit(EXIT_FAILURE);}node->data = ch;node->lchild = CreateBiTree(); // 递归创建左子树node->rchild = CreateBiTree(); // 递归创建右子树node->LTag = Link;node->RTag = Link;return node;}else {return NULL;}
}/*
对二叉树进行线索化
*/
void CreatePreThread(BiThrTree T)
{pre = NULL;if (T){PreThread(T); // 先序线索化if (pre->rchild == NULL){pre->RTag = Thread; // 处理最后一个结点}}
}// 先序遍历 - 边遍历边线索化
void PreThread(BiThrTree T)
{if (T){Visit(T);if (T->LTag == 0){PreThread(T->lchild);}if (T->RTag == 0){PreThread(T->rchild);}}
}void Visit(BiThrNode* q)
//线索化
{if (q->lchild == NULL){q->lchild = pre;q->LTag = Thread;}if (pre != NULL && pre->rchild == NULL){pre->rchild = q;pre->RTag = Thread;}pre = q;
}//找先序后继：根左右
/*
① 若 p->RTag == 1，则 next = p->rchild
② 若 p->RTag == 0，则 如果p有左孩子，next=p的左孩子；如果p没有左孩子，next=p的右孩子
*/
BiThrNode* NextNode(BiThrNode* p)
//寻找p的后继结点
{if (p->RTag == 1){return p->rchild;}if (p->RTag == 0){if (p->lchild && p->LTag == 0)return p->lchild;elsereturn p->rchild;}}
/*
对先序线索二叉树进行先序遍历
*/
void PrintElement(TElemType e)
{printf("%c ", e);
}void PreOrder(BiThrTree T)
{BiThrNode* p = T;for (p; p != NULL; p = NextNode(p)){PrintElement(p->data);}
}

中序线索化

在这里插入图片描述

/*  中序线索化  */
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>#define TElemType char//宏定义，结点中数据域的类型
//枚举，Link为0，Thread为1
typedef enum {Link,Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode {TElemType data;//数据域struct BiThrNode* lchild, * rchild;//左孩子，右孩子指针域PointerTag LTag, RTag;//标志域，枚举类型
}BiThrNode, * BiThrTree;//创建二叉树
BiThrTree CreateBiTree();
//创建线索二叉树
void CreateInThread(BiThrTree T);
//中序遍历线索化
void InThread(BiThrTree T);
void Visit(BiThrNode* q);//寻找p最左下结点
BiThrNode* FirstNode(BiThrNode* p);
//获取后继结点
BiThrNode* NextNode(BiThrNode* p);//对中序线索二叉树进行中序遍历
void PrintElement(TElemType e);
void InOrder(BiThrTree T);//寻找p最右下结点
BiThrNode* LastNode(BiThrNode* p);
//获取前驱结点
BiThrNode* PreNode(BiThrNode* p);
//对中序线索二叉树进行逆向中序遍历
void RevInOrder(BiThrTree T);BiThrNode* pre = NULL;int main() {BiThrTree T = NULL;printf("输入前序二叉树:\n");  // abd#g##e##cf###T = CreateBiTree();CreateInThread(T);printf("对中序线索二叉树进行中序遍历\n");InOrder(T); // d g b e a f cprintf("\n对中序线索二叉树进行逆向中序遍历\n");RevInOrder(T); // c f a e b g dreturn 0;
}//先序创建二叉树
BiThrTree CreateBiTree() {char ch;if (scanf(" %c", &ch) != 1) { // 检查输入是否成功// 输入失败，可能是文件结束符或错误输入exit(EXIT_FAILURE);}if (ch != '#') {BiThrNode* node = (BiThrNode*)malloc(sizeof(BiThrNode)); // 分配内存if (node == NULL) {// 内存分配失败perror("内存分配失败");exit(EXIT_FAILURE);}node->data = ch;node->lchild = CreateBiTree(); // 递归创建左子树node->rchild = CreateBiTree(); // 递归创建右子树node->LTag = Link;node->RTag = Link;return node;}else {return NULL;}
}/*
对二叉树进行线索化
*/
void CreateInThread(BiThrTree T)
{pre = NULL;if (T){InThread(T); // 中序线索化if (pre->rchild == NULL){pre->RTag = Thread; // 处理最后一个结点}}
}// 中序遍历 - 边遍历边线索化
void InThread(BiThrTree T)
{if (T){InThread(T->lchild);Visit(T);InThread(T->rchild);}
}void Visit(BiThrNode* q)
//线索化
{if (q->lchild == NULL){q->lchild = pre;q->LTag = Thread;}if (pre != NULL && pre->rchild == NULL){pre->rchild = q;pre->RTag = Thread;}pre = q;
}//找中序后继：左根右
/*
① 若 p->RTag == 1，则 next = p->rchild
② 若 p->RTag == 0，则 next = p的右子树最左下结点
*/
BiThrNode* FirstNode(BiThrNode* p)
//寻找p最左下结点
{while (p->LTag == 0){p = p->lchild;}return p;
}
BiThrNode* NextNode(BiThrNode* p)
//寻找p的后继结点
{if (p->RTag == 0){return FirstNode(p->rchild);//寻找p的右子树最左下结点}else{return p->rchild;}
}/*
对中序线索二叉树进行中序遍历
*/
void PrintElement(TElemType e)
{printf("%c ", e);
}void InOrder(BiThrTree T)
{BiThrNode* p = FirstNode(T);for (p; p != NULL; p = NextNode(p)){PrintElement(p->data);}
}//找中序前驱：左根右
/*
① 若 p->LTag == 1，则 pre = p->lchild
② 若 p->LTag == 0，则 pre = p的左子树最右下结点
*/
BiThrNode* LastNode(BiThrNode* p)
//寻找p最右下结点
{while (p->RTag == 0){p = p->rchild;}return p;
}
BiThrNode* PreNode(BiThrNode* p)
//寻找p的前驱结点
{if (p->LTag == 0){return LastNode(p->lchild);//寻找p的左子树最右下结点}else{return p->lchild;}
}
/*
对中序线索二叉树进行逆向中序遍历
*/
void RevInOrder(BiThrTree T)
{BiThrNode* p = LastNode(T);for (p; p != NULL; p = PreNode(p)){PrintElement(p->data);}
}

后序线索化

/*  后序线索化  */
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>#define TElemType char//宏定义，结点中数据域的类型
//枚举，Link为0，Thread为1
typedef enum {Link,Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode {TElemType data;//数据域struct BiThrNode* lchild, * rchild;//左孩子，右孩子指针域PointerTag LTag, RTag;//标志域，枚举类型
}BiThrNode, * BiThrTree;//创建二叉树
BiThrTree CreateBiTree();
//创建线索二叉树
void CreatePostThread(BiThrTree T);
//后序遍历线索化
void PostThread(BiThrTree T);
void Visit(BiThrNode* q);//寻找前驱
BiThrNode* PreNode(BiThrNode* p);
//逆向遍历
void PrintElement(TElemType e);
void RevPostOrder(BiThrTree T);BiThrNode* pre = NULL;int main() {BiThrTree T = NULL;printf("输入前序二叉树:\n");  // abd#g##e##cf###T = CreateBiTree();CreatePostThread(T);//正序：g d e b f c a//逆序：a c f b e d gRevPostOrder(T);return 0;
}//先序创建二叉树
BiThrTree CreateBiTree() {char ch;if (scanf(" %c", &ch) != 1) { // 检查输入是否成功// 输入失败，可能是文件结束符或错误输入exit(EXIT_FAILURE);}if (ch != '#') {BiThrNode* node = (BiThrNode*)malloc(sizeof(BiThrNode)); // 分配内存if (node == NULL) {// 内存分配失败perror("内存分配失败");exit(EXIT_FAILURE);}node->data = ch;node->lchild = CreateBiTree(); // 递归创建左子树node->rchild = CreateBiTree(); // 递归创建右子树node->LTag = Link;node->RTag = Link;return node;}else {return NULL;}
}/*
对二叉树进行线索化
*/
void CreatePostThread(BiThrTree T)
{pre = NULL;if (T){PostThread(T); // 后序线索化if (pre->rchild == NULL){pre->RTag = Thread; // 处理最后一个结点}}
}// 后序遍历 - 边遍历边线索化
void PostThread(BiThrTree T)
{if (T){PostThread(T->lchild);PostThread(T->rchild);Visit(T);}
}void Visit(BiThrNode* q)
//线索化
{if (q->lchild == NULL){q->lchild = pre;q->LTag = Thread;}if (pre != NULL && pre->rchild == NULL){pre->rchild = q;pre->RTag = Thread;}pre = q;
}//找后序前驱：左右根
/*
① 若 p->LTag == 1，则 pre = p->lchild
② 若 p->LTag == 0，则 如果p有右孩子，pre=p的右孩子；如果p没有右孩子，pre=p的左孩子
*/BiThrNode* PreNode(BiThrNode* p)
//寻找p的前驱结点
{if (p->LTag == 1){return p->lchild;//寻找p的左子树最右下结点}else{if (p->rchild && p->RTag == 0){return p->rchild;}else{return p->lchild;}}
}
/*
对后序线索二叉树进行逆向的后序遍历
*/
void PrintElement(TElemType e)
{printf("%c ", e);
}void RevPostOrder(BiThrTree T)
{BiThrNode* p = T;for (p; p != NULL; p = PreNode(p)){PrintElement(p->data);}
}

6.4 树和森林

6.4.1 树的存储结构

双亲表示法（顺序存储）

在这里插入图片描述

#define MAX_TREE_SIZE 100   //树中最多结点数
typedef char ElemType;
typedef struct {            //结点结构ElemType data;          //数据元素int parent;             //双亲位置域
}PTNode;typedef struct {                   //树结构PTNode nodes[MAX_TREE_SIZE];  int r, n;                      //根的位置和结点数
}PTree;

可以根据结点的parent 指针很容易找到它的双亲结点，所用的时间复杂度为0(1)，直到parent为-1时，表示找到了树结点的根。
要找到结点的孩子只能遍历整个结构。

孩子表示法（顺序+链式存储）

在这里插入图片描述

#define MAX_TREE_SIZE 100   //树中最多结点数
typedef char ElemType;typedef struct CTNode{   //孩子结点int child;struct CTNode* next;
}* ChildPtr;typedef struct {ElemType data;ChildPtr firstchild;  //孩子链表头指针
}CTBox;typedef struct {CTBox nodes[MAX_TREE_SIZE];int n, r; //结点数和根的位置
}CTree;

查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树就对头结点的数组循环即可。但是查找某个结点的双亲, 需要整棵树遍历才行。

孩子兄弟表示法（链式存储）

在这里插入图片描述

typedef struct CSNode{  ElemType data;struct CSNode * firstchild, *nextsibling;
}CSNode, * CSTree;

6.4.2 森林与二叉树的转换

树转换为二叉树
森林转化为二叉树
二叉树转化为森林

6.4.3 树和森林的遍历

树的遍历

1️⃣先根遍历 / 深度优先遍历

先访问树的根结点，然后依次先根遍历根的每棵子树

2️⃣后根遍历 / 深度优先遍历

先依次后根遍历每棵子树，然后访问根结点

3️⃣层次遍历(用队列实现) / 广度优先遍历

①若树非空，则根节点入队

②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

③重复②直到队列为空
森林的遍历

1️⃣先序遍历

若森林为非空，则按如下规则进行遍历:

访问森林中第一棵树的根结点。

先序遍历第一棵树中根结点的子树森林。

先序遍历除去第一棵树之后剩余的树构成的森林。

2️⃣中序遍历

若森林为非空，则按如下规则进行遍历:

中序遍历森林中第一棵树的根结点的子树森林。

访问第一棵树的根结点。

中序遍历除去第一棵树之后剩余的树构成的森林。

6.5 树与等价问题

6.5.1 等价定义

等价关系

A是一个非空集，R是A上的一个二元关系，若R有自反性对称性、传递性，则说R是A上的等价关系。

设R是集合A上的一个二元关系，即R ⊆ A x A。
定义1:对于任意的x∈A,均有(x,x)∈R, 则称关系R有自反性或称R是A上的自反关系。
定义2: 对于任意的x,y∈A,若(x,y)∈R,就有(y,x)∈ R,则称关系R有对称性，或称R是A上的对称关系。
定义3: 对于任意的x,y,z∈A,若(x,y)∈ R且(y,z)∈R,就有(x,z)∈R,则称关系R有传递性,或称R是A上的传递关系。
等价类

设R是集合S的等价关系。对任何x∈S，由[x]_R = {y|y∈S ∧ xRy} 给出的集合[ x ]_R ⊆ S 称为由于x ∈ S生成的一个R等价类。

（设R是定义在集合A上的等价关系。与A中的一个元素a有关系的所有元素的集合叫作a的等价类。A的关于R的等价类记作[a]_R。当只考虑一个关系时，我们将省去下标R并把这个等价类写作[a]。）

若R是集合S上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分，即可按R将S划分为若干不相交的子集S₁, S₂,…,他们的并为S，则这些子集S_i便为S的等价类。

6.5.2 划分等价类的方法

(1) 令S中每个元素各自形成一个只含单个成员的子集，记作 S₁, S₂ , …, S_n。

(2) 重复读入m个偶对，对每个读入的偶对 (x,y) 判定所属子集。

假设 x∈S_i，y∈S_j，若 S_i ≠ S_j，则将S_i并入S_j并置S_i为空（或将S_j并入S_i并置 S_j空）。

(3) 当m个偶对都被处理过后， S₁, S₂ , …, S_n中所有非空子集即为S的R等价类。

6.5.3 划分等价类的具体操作 - 并查集MFSet

其一是构造只含单个成员的集合；
其二是判定某个单元素所在子集；（查）
其三是归并两个互不相交的集合为一个集合。（并）

MFSet的ADT：

ADT MFSet{数据对象： 若设S是MFSet型的集合，则它由 n(n>O)个子集Si, (i = 1，2，... ，n) 构成，每个子集的成员都是子界[-maxnumber .. maxnumber 内的整数；数据关系： S1∪S2∪ … ∪Sn=S Si⊂S(i=l,2,•••,n)基本操作：Initial(&S, n, x1 , x2 ，……，xn）；操作结果：初始化操作。构造一个由 个子集（每个子集只含单个成员 xi) 构成的集合SFind(S, x); 初始条件：S是已存在的集合， x是S中某个子集的成员。操作结果：查找函数。确定S中x所属子集SiMerge(&S, i, j);初始条件：Si,Sj是S中的两个互不相交的非空集合。操作结果：归并操作。将Si和Sj中的一个并入另一个中
}ADT MFSet;

6.5.4 用树型结构表示集合

以森林F =（ T₁ , T₂ , . . . , T_n ）表示MFSet型的集合S

森林中的每一棵树T_i ( T₁ , T₂ , . . . , T_n )表示S中的一个元素——子集 S_i(S_i ⊂ S, i= 1,2, …,n)

树中的每个结点表示对应子集S_i中的一个成员x

令每个结点含有一个指向其双亲的指针，并约定根结点的成员兼作子集的名字

以采用双亲表示法来作树的存储结构

由于各子集成员均不相同，"并操作"只需将一棵子集树的根指向另一子集树的根即可；
完成"查找"某个成员所在集合的操作，只需从该成员结点出发，顺链而进，直至找到树的根结点为止．。

// ---- 树的双亲表存储表示 ----
#define MAX_TREE_SIZE 100   //树中最多结点数
typedef char ElemType;
typedef struct {            //结点结构ElemType data;          //数据元素int parent;             //双亲位置域
}PTNode;typedef struct {                   //树结构PTNode nodes[MAX_TREE_SIZE];  int r, n;                      //根的位置和结点数
}PTree;//---- MFSet的树的双亲存储表示 ----
typedef PTree MFSet;

6.5.5 并查集及其优化

优化前最坏的时间复杂度

查：=最坏树高=O(n)

将n个独立元素通过多次Union合并为一个集合：O(n²)

并优化后树高不超过 ⌊log₂n⌋+1 ，最坏的时间复杂度

查：O(log₂n)

将n个独立元素通过多次Union合并为一个集合：O(nlog₂n)

find优化后最坏的时间复杂度

查：O(α(n))

将n个独立元素通过多次Union合并为一个集合：O(nα(n))

α(n) 是一个增长极其缓慢的函数，对于通常所见到的正整数n而言， α(n) ≤ 4

在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>// ---- 树的双亲表存储表示 ----
#define MAX_TREE_SIZE 100   //树中最多结点数
typedef char ElemType;
typedef struct {            //结点结构ElemType data;          //数据元素int parent;             //双亲位置域
}PTNode;typedef struct {                   //树结构PTNode nodes[MAX_TREE_SIZE];int r, n;                      //根的位置和结点数
}PTree;//---- MFSet的树的双亲存储表示 ----
typedef PTree MFSet;void Initial(MFSet* mfset, ElemType elements[], int parent[], int size)
{mfset->n = size; // 设置结点数mfset->r = -1;   // 假设根节点的双亲位置为-1for (int i = 0; i < size; i++) {mfset->nodes[i].data = elements[i]; // 设置数据元素mfset->nodes[i].parent = parent[i]; // 设置双亲位置}
}// 打印MFSet
void printMFSet(MFSet mfset) {printf("MFSet:\n");for (int i = 0; i < mfset.n; i++) {printf("Node %d: Data = %c, Parent = %d\n", i, mfset.nodes[i].data, mfset.nodes[i].parent);}
}//查 - 找i所属集合的根节点  最坏的时间复杂度O(d), 其中d是树的深度
int Find_MFSet(MFSet s, int i)
{if (i<0 || i>s.n - 1){return -2;}int j;for (j = i; s.nodes[j].parent >= 0; j = s.nodes[j].parent);return j;
}//并 -i，j两个集合合并为一个  时间复杂度O(1)
void Merge_MFSet(MFSet* s, int i, int j)
{if (i<0 || i>(*s).n - 1 || j<0 || j>(*s).n - 1){return -2;}if (i == j){return -2;}(*s).nodes[j].parent = i; //j并到i
}int main() {ElemType elements[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M' };int parent[] = { -1, 0, -1, -1, 1, 1, 2, 3, 3, 3, 4, 4, 7 };int size = sizeof(elements) / sizeof(elements[0]);MFSet myMFSet;Initial(&myMFSet, elements, parent, size);printMFSet(myMFSet);int gen = Find_MFSet(myMFSet, parent[6]);printf("G所在集合的根节点：%d, 根节点为：%c\n", gen, myMFSet.nodes[gen].data);Merge_MFSet(&myMFSet, 0, 2); // C集合合并到A集合printMFSet(myMFSet);int gen1 = Find_MFSet(myMFSet, parent[6]);printf("G所在集合的根节点：%d, 根节点为：%c\n", gen1, myMFSet.nodes[gen1].data);return 0;
}

并优化

在作“并”操作之前先判别子集中所含成员的数目，然后令含成员少的子集树根结点指向含成员多的子集的根

在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>// ---- 树的双亲表存储表示 ----
#define MAX_TREE_SIZE 100   //树中最多结点数
typedef char ElemType;
typedef struct {            //结点结构ElemType data;          //数据元素int parent;             //双亲位置域
}PTNode;typedef struct {                   //树结构PTNode nodes[MAX_TREE_SIZE];int r, n;                      //根的位置和结点数
}PTree;//---- MFSet的树的双亲存储表示 ----
typedef PTree MFSet;void Initial(MFSet* mfset, ElemType elements[], int parent[], int size)
{mfset->n = size; // 设置结点数mfset->r = -1;   // 假设根节点的双亲位置为-1for (int i = 0; i < size; i++) {mfset->nodes[i].data = elements[i]; // 设置数据元素mfset->nodes[i].parent = parent[i]; // 设置双亲位置}
}// 打印MFSet
void printMFSet(MFSet mfset) {printf("MFSet:\n");for (int i = 0; i < mfset.n; i++) {printf("Node %d: Data = %c, Parent = %d\n", i, mfset.nodes[i].data, mfset.nodes[i].parent);}
}//并的优化 
void Mix_MFSet(MFSet* s, int i, int j)
{if (i<0 || i>(*s).n - 1 || j<0 || j>(*s).n - 1){return -2;}if (s->nodes[i].parent > s->nodes[j].parent){//Si 所含成员数比 Sj少s->nodes[j].parent += s->nodes[i].parent;s->nodes[i].parent = j;}else{s->nodes[i].parent += s->nodes[j].parent;s->nodes[j].parent = i;}
}int main() {printf("------------------------优化-----------------------");ElemType elements[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M' };int parent[] = { -6, 0, -2, -5, 1, 1, 2, 3, 3, 3, 4, 4, 7 };int size = sizeof(elements) / sizeof(elements[0]);MFSet myMFSet;Initial(&myMFSet, elements, parent, size);printMFSet(myMFSet);printf("----------------------合并A和C----------------------");Mix_MFSet(&myMFSet, 0, 2);printMFSet(myMFSet);/* printf("----------------------合并C和D----------------------");Mix_MFSet(&myMFSet, 2, 3);printMFSet(myMFSet);*/return 0;
}

查找优化

压缩路径–Find 操作，先找到根节点，再将查找路径上所有结点都挂到根结点下

在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>// ---- 树的双亲表存储表示 ----
#define MAX_TREE_SIZE 100   //树中最多结点数
typedef char ElemType;
typedef struct {            //结点结构ElemType data;          //数据元素int parent;             //双亲位置域
}PTNode;typedef struct {                   //树结构PTNode nodes[MAX_TREE_SIZE];int r, n;                      //根的位置和结点数
}PTree;//---- MFSet的树的双亲存储表示 ----
typedef PTree MFSet;void Initial(MFSet* mfset, ElemType elements[], int parent[], int size)
{mfset->n = size; // 设置结点数mfset->r = -1;   // 假设根节点的双亲位置为-1for (int i = 0; i < size; i++) {mfset->nodes[i].data = elements[i]; // 设置数据元素mfset->nodes[i].parent = parent[i]; // 设置双亲位置}
}// 打印MFSet
void printMFSet(MFSet mfset) {printf("MFSet:\n");for (int i = 0; i < mfset.n; i++) {printf("Node %d: Data = %c, Parent = %d\n", i, mfset.nodes[i].data, mfset.nodes[i].parent);}
}//查 - 优化（压缩路径）
int Find_MFSet(MFSet *s, int i)
{if (i<0 || i>s->n-1){return -2;}int root = i;while (s->nodes[root].parent >= 0){root = s->nodes[root].parent;}while (i != root){int t = s->nodes[i].parent;s->nodes[i].parent = root;i = t;}return root;
}int main() {ElemType elements[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M' };int parent[] = { -1, 0, -1, -1, 1, 1, 2, 3, 3, 3, 4, 4, 7 };int size = sizeof(elements) / sizeof(elements[0]);MFSet myMFSet;Initial(&myMFSet, elements, parent, size);printMFSet(myMFSet);printf("----------------------查找优化----------------------\n");int gen = Find_MFSet(&myMFSet, 11);printf("G所在集合的根节点：%d, 根节点为：%c\n", gen, myMFSet.nodes[gen].data);printMFSet(myMFSet);return 0;
}

6.6 赫夫曼树及其应用

6.6.1 最优二叉树(赫夫曼树)

从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。
树的路径长度是从树根到每一结点的路径长度之和。
树的带权路径长度（Weighted Path Length of Tree，简记为WPL）：定义为树中所有叶子结点的带权路径长度之和.
- 结点的权值：在一些应用中，赋予树中结点的一个有某种意义的实数。
- 结点的带权路径长度：从该结点到树根之间的路径长度与该结点上权值的乘积。
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树（Full Binary Tree）或者哈夫曼树（Huffman Tree）。

特点：
- 叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。
- 最优二叉树中，权越大的叶子离根越近。
- 最优二叉树的形态不唯一，WPL最小。

6.6.2 赫夫曼编码

任一字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀码

在这里插入图片描述

//方法一 - 从叶子到根
void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n) {*HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));char* cd = (char*)malloc(n * sizeof(char)); //存放结点哈夫曼编码的字符串数组cd[n - 1] = '\0';//字符串结束符for (int i = 1; i <= n; i++) {//cd数组的下标，用于逆序存储到cd数组int start = n - 1;//当前结点在数组中的位置int c = i;//当前结点的父结点在数组中的位置int j = HT[i].parent;// 一直寻找到根结点while (j != 0) {// 如果该结点是父结点的左孩子则对应路径编码为0，否则为右孩子编码为1if (HT[j].lchild == c)cd[--start] = '0';elsecd[--start] = '1';//以父结点为孩子结点，继续朝树根的方向遍历c = j;j = HT[j].parent;}//跳出循环后，cd数组中从下标 start 开始，存放的就是该结点的哈夫曼编码(*HC)[i] = (char*)malloc((n - start) * sizeof(char));strcpy((*HC)[i], &cd[start]);}//使用malloc申请的cd动态数组需要手动释放free(cd);
}

在这里插入图片描述

// 方法二： 从根到叶子结点
void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n) {*HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));int m = 2 * n - 1;int p = m;int cdlen = 0;char* cd = (char*)malloc(n * sizeof(char));for (int i = 1; i <= m; i++) {HT[i].weight = 0;}//一开始 p 初始化为 m，也就是从树根开始。一直到p为0while (p) {//如果当前结点一次没有访问，进入这个if语句if (HT[p].weight == 0) {HT[p].weight = 1;//重置访问次数为1//如果有左孩子，则访问左孩子，并且存储走过的标记为0if (HT[p].lchild != 0) {p = HT[p].lchild;cd[cdlen++] = '0';}//当前结点没有左孩子，也没有右孩子，说明为叶子结点，直接记录哈夫曼编码else if (HT[p].rchild == 0) {(*HC)[p] = (char*)malloc((cdlen + 1) * sizeof(char));cd[cdlen] = '\0';strcpy((*HC)[p], cd);}}//如果weight为1，说明访问过一次，即是从其左孩子返回的else if (HT[p].weight == 1) {HT[p].weight = 2;//设置访问次数为2//如果有右孩子，遍历右孩子，记录标记值 1if (HT[p].rchild != 0) {p = HT[p].rchild;cd[cdlen++] = '1';}}//如果访问次数为 2，说明左右孩子都遍历完了，返回父结点else {HT[p].weight = 0;p = HT[p].parent;--cdlen;}}
}

存储结构

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include<string.h>typedef struct {unsigned int weight;unsigned int parent, lchild, rchild;
}HTNode, * HuffmanTree;  //动态分配数组存储赫夫曼树typedef char** HuffmanCode;   //动态分配数组存储赫夫曼编码表void Select(HuffmanTree HT, int end, int* s1, int* s2)
{int min1, min2;//遍历数组初始下标为 1int i = 1;/*找到还没构建树的结点*///i取值[1,9) -> [1,n+1) -> [1,n]while (HT[i].parent != 0 && i < end) {i++;}min1 = HT[i].weight;*s1 = i;i++;while (HT[i].parent != 0 && i < end) {i++;}//对找到的两个结点比较大小，min2为大的，min1为小的if (HT[i].weight < min1) {min2 = min1;*s2 = *s1;min1 = HT[i].weight;*s1 = i;}else {min2 = HT[i].weight;*s2 = i;}//两个结点和后续的所有未构建成树的结点做比较for (int j = i + 1; j < end; j++){//如果有父结点，直接跳过，进行下一个if (HT[j].parent != 0) {continue;}//如果比最小的还小，将min2=min1，min1赋值新的结点的下标if (HT[j].weight < min1) {min2 = min1;min1 = HT[j].weight;*s2 = *s1;*s1 = j;}//如果介于两者之间，min2赋值为新的结点的位置下标else if (HT[j].weight >= min1 && HT[j].weight < min2) {min2 = HT[j].weight;*s2 = j;}}
}void CreateHuffmanTree(HuffmanTree* HT, int* w, int n)
{if (n <= 1) return; // 如果只有一个编码就相当于0int m = 2 * n - 1; // 赫夫曼树总结点数，n + (n - 1)【 4个结点-创建的赫夫曼树总共需要7个结点】*HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); // 0号位置不用// 初始化赫夫曼树中的所有结点if (*HT){for (int i = 1; i <= n; i++){((*HT) + i)->weight = *(w + i - 1);((*HT) + i)->parent = 0;((*HT) + i)->lchild = 0;((*HT) + i)->rchild = 0;}//从树组的下标 n+1 开始初始化赫夫曼树中除叶子结点外的结点for (int i = n + 1; i <= m; i++){((*HT) + i)->weight = 0;((*HT) + i)->parent = 0;((*HT) + i)->lchild = 0;((*HT) + i)->rchild = 0;}//构建赫夫曼树for (int i = n + 1; i <= m; i++){int s1, s2;Select(*HT, i, &s1, &s2);(*HT)[s1].parent = i; (*HT)[s2].parent = i;(*HT)[i].lchild = s1;(*HT)[i].rchild = s2;(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;}}}
//方法一实现：
void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n)
{ // w存放n个字符的权值（均 >O), 构造赫夫曼树HT, 并求出n个字符的赫夫曼编码HC*HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));char* cd = (char*)malloc(n * sizeof(char)); //存放结点哈夫曼编码的字符串数组cd[n - 1] = '\0';//字符串结束符for (int i = 1; i <= n; i++) {//从叶子结点出发，得到的哈夫曼编码是逆序的，需要在字符串数组中逆序存放int start = n - 1;//当前结点在数组中的位置int c = i;//当前结点的父结点在数组中的位置int j = HT[i].parent;// 一直寻找到根结点while (j != 0) {// 如果该结点是父结点的左孩子则对应路径编码为0，否则为右孩子编码为1if (HT[j].lchild == c)cd[--start] = '0';elsecd[--start] = '1';//以父结点为孩子结点，继续朝树根的方向遍历c = j;j = HT[j].parent;}//跳出循环后，cd数组中从下标 start 开始，存放的就是该结点的哈夫曼编码(*HC)[i] = (char*)malloc((n - start) * sizeof(char));strcpy((*HC)[i], &cd[start]);}//使用malloc申请的cd动态数组需要手动释放free(cd);
}//打印哈夫曼编码的函数
void PrintHuffmanCode(HuffmanCode htable, int* w, int n)
{printf("Huffman code : \n");for (int i = 1; i <= n; i++)printf("%d code = %s\n", w[i - 1], htable[i]);
}
int main()
{int w[8] = { 5,29,7,8,14,23,3,11 };int n = 8;HuffmanTree htree;HuffmanCode htable;CreateHuffmanTree(&htree, w, n);HuffmanCoding(htree, &htable, n);PrintHuffmanCode(htable, w, n);return 0;
}

在这里插入图片描述

6.7 回溯法与树的遍历

回溯法也可以叫做回溯搜索法，它是⼀种搜索的⽅式

回溯法（backtracking）是设计递归过程的一种重要方法,它的求解过程实质上是一个先序遍历一棵“状态树”的过程,只是这棵树不是遍历前预先建立的,而是隐含在遍历过程中。回溯是递归的副产品，只要有递归就会有回溯。

可以解决的问题：

组合：N个数⾥⾯按⼀定规则找出k个数的集合（无序）
切割：⼀个字符串按⼀定规则有⼏种切割⽅式
子集：⼀个N个数的集合⾥有多少符合条件的⼦集
排列：N个数按⼀定规则全排列，有⼏种排列⽅式（有序）
棋盘：N皇后，解数独等等

模板框架：

在这里插入图片描述

void backtracking(参数) {if (终⽌条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

组合问题

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例: 输⼊: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>typedef struct {int** result;int* path;int resultSize;int pathSize;
} Solution;void backtracking(Solution* sol, int n, int k, int startIndex) {if (sol->pathSize == k) {sol->result[sol->resultSize] = (int*)malloc(k * sizeof(int));if (sol->result[sol->resultSize]){for (int i = 0; i < k; i++) {sol->result[sol->resultSize][i] = sol->path[i];}sol->resultSize++;return;}return;}for (int i = startIndex; i <= n; i++) {sol->path[sol->pathSize] = i;sol->pathSize++;backtracking(sol, n, k, i + 1);sol->pathSize--; // 回溯，撤销处理的节点}
}void combine(Solution* sol, int n, int k) {sol->resultSize = 0;sol->pathSize = 0;sol->result = (int**)malloc(10000 * sizeof(int*)); // 假设结果集不会超过10000个sol->path = (int*)malloc(k * sizeof(int));backtracking(sol, n, k, 1);
}void printSolution(Solution* sol, int k) {for (int i = 0; i < sol->resultSize; i++) {for (int j = 0; j < k; j++) {printf("%d ", sol->result[i][j]);}printf("\n");free(sol->result[i]); // 释放每一行的内存}free(sol->result); // 释放结果集的内存free(sol->path); // 释放路径的内存
}int main() {Solution sol;int n = 4;int k = 2;combine(&sol, n, k);printSolution(&sol, k);return 0;
}

剪枝操作

在这里插入图片描述

void backtracking(Solution* sol, int n, int k, int startIndex) {if (sol->pathSize == k) {sol->result[sol->resultSize] = (int*)malloc(k * sizeof(int));if (sol->result[sol->resultSize]){for (int i = 0; i < k; i++) {sol->result[sol->resultSize][i] = sol->path[i];}sol->resultSize++;return;}return;}for (int i = startIndex; i <= n - (k - sol->pathSize) + 1; i++) {sol->path[sol->pathSize] = i;sol->pathSize++;backtracking(sol, n, k, i + 1);sol->pathSize--; // 回溯，撤销处理的节点}
}

组合总和

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。说明：所有数字都是正整数。解集不能包含重复的组合。输⼊: k = 2, n = 4

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>typedef struct {int** result;int* path;int resultSize;int pathSize;
} Solution;// targetSum：⽬标和，也就是题⽬中的n。
// k：题⽬中要求k个数的集合。
// sum：已经收集的元素的总和，也就是path⾥元素的总和。
// startIndex：下⼀层for循环搜索的起始位置。
void backtracking(Solution* sol, int targetSum, int n, int k, int sum, int startIndex) {if (sol->pathSize == k) {if (sum > targetSum) return; // 剪枝操作if (sum == targetSum){sol->result[sol->resultSize] = (int*)malloc(k * sizeof(int));if (sol->result[sol->resultSize]){for (int i = 0; i < k; i++) {sol->result[sol->resultSize][i] = sol->path[i];}sol->resultSize++;return;}}return;}// 剪枝操作for (int i = startIndex; i <= n - (k - sol->pathSize) + 1; i++) {sum += i;sol->path[sol->pathSize] = i;sol->pathSize++;backtracking(sol, targetSum, n, k, sum, i + 1);sum -= i;sol->pathSize--; // 回溯，撤销处理的节点}}void combine(Solution* sol, int n, int k, int targetSum) {sol->resultSize = 0;sol->pathSize = 0;sol->result = (int**)malloc(10000 * sizeof(int*)); // 假设结果集不会超过10000个sol->path = (int*)malloc(k * sizeof(int));backtracking(sol, targetSum, n, k, 0, 1);
}void printSolution(Solution* sol, int k) {for (int i = 0; i < sol->resultSize; i++) {for (int j = 0; j < k; j++) {printf("%d ", sol->result[i][j]);}printf("\n");free(sol->result[i]); // 释放每一行的内存}free(sol->result); // 释放结果集的内存free(sol->path); // 释放路径的内存
}int main() {Solution sol;int n = 9;int target_sum = 11;int k = 3;combine(&sol, n, k, target_sum);printSolution(&sol, k);return 0;
}

N皇后

在n×n格的棋盘上放置彼此不受攻击的n个皇后

皇后的约束条件： 1. 不能同⾏ 2. 不能同列 3. 不能同斜线

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>bool isSafe(int* queens, int row, int col) {for (int i = 0; i < row; i++) {if (queens[i] == col || abs(row - i) == abs(col - queens[i])) {return false;}}return true;
}void backtrack(int* queens, int row, int N, char*** result, int* resultSize) {if (row == N) {// 当前解已经找到，将其存入结果数组result[*resultSize] = (char**)malloc(N * sizeof(char*));for (int i = 0; i < N; i++) {result[*resultSize][i] = (char*)malloc((N + 1) * sizeof(char));for (int j = 0; j < N; j++) {result[*resultSize][i][j] = (queens[i] == j) ? 'Q' : '.';}result[*resultSize][i][N] = '\0';}(*resultSize)++;return;}for (int col = 0; col < N; col++) {if (isSafe(queens, row, col)) {queens[row] = col;backtrack(queens, row + 1, N, result, resultSize);queens[row] = -1;}}
}char*** solveNQueens(int N, int* returnSize) {char*** result = (char***)malloc(1000 * sizeof(char**));*returnSize = 0;int* queens = (int*)malloc(N * sizeof(int));for (int i = 0; i < N; i++) {queens[i] = -1;}backtrack(queens, 0, N, result, returnSize);free(queens); // 释放queens数组return result;
}// 打印所有合法的棋盘配置
void printSolutions(char*** result, int N, int returnSize) {for (int i = 0; i < returnSize; i++) {for (int row = 0; row < N; row++) {printf("%s\n", result[i][row]);}printf("\n");for (int row = 0; row < N; row++) {free(result[i][row]); // 释放每一行的内存}free(result[i]); // 释放二维数组的内存}free(result); // 释放结果集的内存
}int main() {int N = 4; // 例如，解决4皇后问题int returnSize;char*** result = solveNQueens(N, &returnSize);printf("Total %d solutions for %d Queens problem:\n", returnSize, N);printSolutions(result, N, returnSize);return 0;
}

6.8 树的计数

含有n个结点的不相似的二叉树有 $\frac{1}{n+1} C^n_{2n}$ 。

在这里插入图片描述

参考：

教材：

严蔚敏《数据结构》（C语言版）.pdf

离散数学及其应用（原书第8版） (Kenneth H.Rosen) .pdf

《代码随想录》回溯算法（V3.0）.pdf

视频：

https://www.bilibili.com/video/BV1Zf4y1a77g/?spm_id_from=333.788&vd_source=a89593e8d33b31a56b894ca9cad33d33

https://www.bilibili.com/video/BV1b7411N798/?p=51&spm_id_from=333.880.my_history.page.click&vd_source=a89593e8d33b31a56b894ca9cad33d33

https://www.bilibili.com/video/BV1pu411c7pf/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=a89593e8d33b31a56b894ca9cad33d33

https://www.bilibili.com/video/BV17F411T7Ao?p=195&vd_source=a89593e8d33b31a56b894ca9cad33d33

博客：

https://blog.csdn.net/Real_Fool_/article/details/113930623

https://blog.csdn.net/m0_73633088/article/details/133443742

https://blog.csdn.net/wangrunmin/article/details/7831318

https://blog.csdn.net/Colorful___/article/details/133603913

https://blog.51cto.com/u_13360/6732847

https://zhuanlan.zhihu.com/p/600665635

https://blog.csdn.net/crr411422/article/details/129932889

https://blog.51cto.com/u_15773967/6148952

https://blog.csdn.net/2401_82584055/article/details/138349195

https://mp.weixin.qq.com/s?__biz=Mzg5MjkxNTA5MA==&mid=2247484467&idx=2&sn=3ea1749b1c7c301289a40dac4497e87e&chksm=c03798cef74011d8ead16e27ebea8e3a1df2a9a0242385d328f0ec05973e9b12ef1fa7254e14&scene=27

工具：

https://www.cs.usfca.edu/~galles/visualization/DisjointSets.html