408数据结构第五章树与二叉树-EW帮帮网

微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

408数据结构

第一章绪论
第二章线性表
绪论、线性表选择题做题笔记
第三章栈、队列和数组
栈、队列和数组选择题做题笔记
第四章串
第五章树与二叉树

文章目录

408数据结构
前言
一、树的基本内容
- （1）基本概念
- 1.树的分类
- （2）基本术语
- 1.结点之间的关系描述
- 2.结点、树的属性描述
- 3.有序树、无序树
- 4.森林
二、树的常考性质
三、二叉树
- （1）二叉树的分类
- （2）二叉树的五种形态
- （3）几个特殊的二叉树
- 1.满二叉树
- 2.完全二叉树
- 3.二叉排序树
- 4.平衡二叉树
四、二叉树的常考性质
五、二叉树的存储结构
六、二叉树的遍历
- （1）前序遍历（NLR）
- （2）中序遍历（LNR）
- （3）后序遍历（LRN）
- （4）层次遍历
七、遍历的应用：反推序列
- （1）问题一：单独知道一种遍历结果能不能反推序列
- （2）问题二：知道哪些遍历结果才能得到唯一的树
- 1.前序+中序
- 2.后序+中序
- （3）层序+中序
八、线索二叉树
- （1）普通二叉树的缺陷--线索二叉树应运而生
- （2）线索二叉树
- 1.中序线索二叉树
- 2.先序线索二叉树
- 3.后序线索二叉树
九、树的存储结构
- （1）基于顺序存储的双亲表示法
- 1. 树的双亲表示法
- 2. 拓展：森林的双亲表示法
- 3.双亲表示法的优缺点
- （2）基于顺序+链式的孩子表示法
- 1. 普通树的孩子表示法
- 2. 拓展：森林的孩子表示法
- 3. 孩子表示法的优缺点
- （3）基于链式存储的孩子兄弟表示法
- 1. 普通树的孩子兄弟表示法
- 2. 森林的孩子兄弟表示法
十、树、森林、二叉树的转换
- （1）树转二叉树
- （2）森林转二叉树
- （3）二叉树转树
- （4）二叉树转森林
十一、树和森林的遍历
- （1）树的遍历
- 1. 先根遍历/树的深度优先遍历
- 2. 后根遍历/树的深度优先遍历
- 3. 层序遍历/树的广度优先遍历
- （2）森林的遍历
- 1. 先序遍历
- 2. 中序遍历
十二、哈夫曼树
- （1）带权路径长度
- （2）哈夫曼树的定义
- （3）哈夫曼树的构造（重点）
- （4）哈夫曼编码
十二、并查集（Disjoint Set）
- （1）如何表示集合关系
- 1. 对于集合常见的操作一：判断一个元素属于哪一个集合（“查”操作）
- 2. 对于集合常见的操作二：判断两个元素是否属于同一个集合
- 3. 对于集合常见的操作三：将两个集合合并成一个集合
- （2）并查集的代码实现
- （3）并查集的优化
- （4）并查集的终极优化
总结

前言

本章内容较多，讲解了树、森林、并查集等多种数据结构及其操作原理与代码实现

一、树的基本内容

（1）基本概念

请添加图片描述

叶子结点：没有后继的结点，也叫终端结点
分支结点：有后继的结点，也叫非终端结点
除了根结点外，任何一个结点都有且仅有一个前驱
每个结点可以有0个或多个后继
若为非空树，则有且仅有一个根节点
子树

1.树的分类

（1）空树：结点数为0的树
（2）非空树：结点数不为0的树

（2）基本术语

1.结点之间的关系描述

请添加图片描述

（1）祖先结点：从该结点开始沿着边一直往上，经过的结点即为该结点的祖先结点
【例如】M的祖先结点就是：H、三叔、爷爷
（2）子孙结点：从该结点出发，沿着各条边往下，经过的结点即为该结点的子孙结点
【例如】三叔的子孙结点是：H、I、J、M
（3）双亲结点（父结点）：该结点的直接前驱结点
（4）孩子结点：该结点的直接后继
（5）兄弟结点：同一个父节点的结点之间是兄弟结点
（6）堂兄弟结点：父结点的兄弟结点的孩子结点
（7）结点之间的路径：两个结点之间的边，从上往下的单向路径
（8）路径长度：路径经过的边数

2.结点、树的属性描述

请添加图片描述

（1）结点的层次/深度：根结点所在层位第一层，从上往下层数依次+1
【例如】A的深度为1，B\C\D的深度为2，以此类推
（2）结点的高度：最下面一层的高度为1（注意：并不是叶子结点的高度就是1）
【举例】K\L\M的高度是1，E\F\G\H\I\J的高度是2
（3）树的高度（深度）：总共的层数
【例如】上图的深度就是4
（4）结点的度：结点的孩子个数/分支个数，叶子节点的度为0
【例如】B的度是2，C的度是1
（5）树的度：各结点的度的最大值

3.有序树、无序树

（1）有序树：从逻辑上，各子树从左到右是有次序的
（2）无序树：从逻辑上，各子树从左到右是五次序的

4.森林

（1）森林的概念：m棵互不相交的树的集合

二、树的常考性质

（1）结点数=总度数+1
（2）度为m的树 vs m叉树

3.结论三：

4.结论四：

5.结论五：

6.结论六：

【推导】

三、二叉树

二叉树是n（非负整数）个结点的有限集合，且二叉树是有序树

（1）二叉树的分类

（1）空二叉树，即n=0
（2）非空二叉树：由一个根节点和两个互不相交的被称为根的左子树和右子树组成。左右子树又分别是一棵二叉树

（2）二叉树的五种形态

空二叉树
只有根节点的二叉树
左子树非空的二叉树
右子树非空的二叉树
左右子树都非空的二叉树

（3）几个特殊的二叉树

1.满二叉树

请添加图片描述

只有最后一层有叶子结点
不存在度为1的结点
按层序从1开始开始编号，结点i的左孩子是2i，右孩子是2i+1，结点i的父节点是[i/2]（如果有父节点的话）

2.完全二叉树

请添加图片描述

只有最后两层可能有叶子结点
最多只有一个度为1的结点
按层序从1开始开始编号，结点i的左孩子是2i，右孩子是2i+1，结点i的父节点是[i/2]（如果有父节点的话）
当i<=[n/2]时，为分支结点，i>[n/2]时，为叶子结点

3.二叉排序树

（1）二叉排序树是具有下面性质的二叉树
左子树上所有结点的关键字均小于根节点的关键字
右子树上所有结点的关键字均大于根节点的关键字

4.平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1
平衡二叉树有更高的搜索效率

四、二叉树的常考性质

考点一：
考点二：
考点三：
考点四：
考点五：

请添加图片描述

考点六：

五、二叉树的存储结构

二叉树的顺序存储与初始化

#define MaxSize 100
struct TreeNode {
	int value;//结点中的数据元素
	bool isEmpty;//结点数是否为空
};

bool InitTree(TreeNode T[])
{
	for (int i = 0; i < MaxSize; i++)
	{
		T[i].isEmpty = true;
	}
	return true;
}

在这里插入图片描述

对于非完全二叉树：将结点补齐成完全二叉树进行存储即可
缺点：大量闲置空间

链式存储的树

struct ElemType
{
	int value;
};
typedef struct BiTNode {
	ElemType data;//数据域
	struct BiTNode* lchild, * rchild;//左右孩子指针
}BiTNode,*BiTree;

n个结点的二叉链表共有n+1个空链域，这些域可用于构造线索二叉树

二叉链表的初始化

bool InitTree(BiTree root)
{
	root = (BiTree)malloc(sizeof(BiTNode));
	if (root == NULL)
	{
		return false;
	}

	root->data = { 1 };
	root->lchild = NULL;
	root->rchild = NULL;

	return true;
}

三叉链表

typedef struct three_BiTNode {
	ElemType data;
	struct BiTNode* lchild, * rchild;
	struct BiTNode* parent;
}BiTNode,*parent;

六、二叉树的遍历

什么是遍历
答：按照某种次序把所有结点都访问一遍

（1）前序遍历（NLR）

void visit(BiTNode* T)
{
	printf("%d",T->data);
 }

void PreOrder(BiTree T)
{
	if (T != NULL)
	{
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

（2）中序遍历（LNR）

void MidOrder(BiTree T)
{
	if (T != NULL)
	{
		MidOrder(T->lchild);
		visit(T);
		MidOrder(T->rchild);
	}
}

（3）后序遍历（LRN）

void PostOrder(BiTree T)
{
	if (T != NULL)
	{
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

遍历练习

请添加图片描述

（4）层次遍历

层次遍历：基于树的层次特性确定的次序规则

在这里插入图片描述

实现思路

（1）初始化一个辅助队列
（2）根节点入队
（3）若队列非空，对头结点出队，访问该结点，并将左右孩子插入队尾（如果有左右孩子的话）
（4）重复（3）的操作，直到队列非空

//链队列的实现
typedef struct LinkNode {
	BiTNode* T;//由于保存结点指针比保存结点本身数据所需空间少，因此直接存指针即可
	struct LinkNode* next;
}LinkNode;

typedef struct {
	LinkNode* front, * rear;
}LinkQueue;

//带头结点链队列的初始化
bool InitLinkQueue(LinkQueue& Q)
{
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next = NULL;
	//初始化时front和rear都指向头结点且标记下一个结点为空
}

bool EnQueue(LinkQueue& Q, BiTNode* T)
{
	LinkNode* q = (LinkNode*)malloc(sizeof(LinkNode));
	q->T = T;
	q->next = NULL;
	Q.rear->next = q;
	Q.rear = q;
	return true;
}

bool Judge_Empty(LinkQueue Q)
{
	if (Q.front == Q.rear)
	{
		return true;
	}
	return false;
}

bool DeQueue(LinkQueue Q,BiTNode*& T)
{
	T = Q.front->T;
	printf("%d\n", Q.front->T->data);
	Q.front = Q.front->next;
	return true;
}

void LevelOrder(BiTree T)
{
	LinkQueue Q;
	InitLinkQueue(Q);//辅助队列使用了链队列
	
	EnQueue(Q, T);
	BiTNode* p = T;
	
	while (!Judge_Empty(Q))
	{
		DeQueue(Q,p);
		if (p->lchild != NULL)
		{
			EnQueue(Q, p->lchild);
		}
		if (p->rchild != NULL)
		{
			EnQueue(Q, p->rchild);
		}
	}
}

七、遍历的应用：反推序列

（1）问题一：单独知道一种遍历结果能不能反推序列

单独知道中序遍历结果
以上三个的前序遍历结果是一样的
单独知道前序遍历结果
单独知道后序遍历结果
单独知道层序遍历结果

结论

一种遍历结果对应着多种不一样的树

（2）问题二：知道哪些遍历结果才能得到唯一的树

在这里插入图片描述

1.前序+中序

原理
举例

在这里插入图片描述

2.后序+中序

原理
举例

（3）层序+中序

原理
举例

八、线索二叉树

（1）普通二叉树的缺陷–线索二叉树应运而生

普通二叉树缺陷算法一：找到一颗树的某个结点在其中序遍历序列中的前驱结点
思路：只能从头到尾进行一次中序遍历，记录当前遍历的结点和上一个结点，直到遍历到所求结点时
普通二叉树缺陷算法二：从指定结点开始进行中序遍历
这个算法是无法实现的，指定结点只有像下一层的指针，中序需要向上的指针，除非从头到尾来一遍或者使用三叉链表

（2）线索二叉树

（1）原理：对于n个结点的二叉树，会有n+1个空链域！可用于记录前驱、后继的信息，没有前驱指向NULL
（2）应用：对于经常需要遍历的二叉树，线索二叉树更方便找某一个结点的前驱和后继

线索二叉树结构体

typedef struct ThreadNode {
	int data;
	struct ThreadNode* lchild, * rchild;
	int ltag, rtag;//当tag=0时，说明指针指向的真的是左孩子，当tag=1时，说明指针指向的是线索（中序前驱和中序后继）
}ThreadNode,*ThreadTree;

1.中序线索二叉树

请添加图片描述

（1）转化方法
1.写出中序遍历的结果
2.根据结果将空链域指向前驱和后驱，实现线索化
（2）中序后继的查找
1.若p->rtag==1;则next=p->rchild;
2.若p->rtag==0;则有以下分析
[分析]我要找他的后继，也就是找谁的前驱是他，由于左中右，因此他的后继应该是他的右子树中第一个被遍历的结点，也就是最左边的结点

中序后继的查找代码

ThreadNode* Firstnode(ThreadNode* p)
{
	while (p->ltag == 0)//注意：肯定有左孩子，只不过是不是真的左孩子而已
	{
		p = p->lchild;
	}
	return p;
}

ThreadNode* NextNode(ThreadNode* p)
{
	if (p->rtag == 0)
	{
		return Firstnode(p->rchild);
	}
	else
	{
		return p->rchild;
	}
}

利用中序后继的查找进行中序遍历

void visit_xiansuo(ThreadNode* p)
{
	printf("%d\n", p->data);
}

void Inorder(ThreadNode *T)
{
	for (ThreadNode* p = Firstnode(T); p != NULL; p = NextNode(p))
	{
		visit_xiansuo(p);
	}
}

（3）中序前驱的查找
1.若p->ltag==1;则prior=p->lchild;
2.若p->ltag==0;则有以下分析
【分析】我要找他的前驱，也就是找谁的后继是他，由于左中右，因此他的前驱应该是他的左子树中最后一个被遍历的结点，也就是最右下角的结点

中序前驱查找代码

ThreadNode* Lastnode(ThreadNode* p)
{
	while (p->ltag == 0)//注意：肯定有左孩子，只不过是不是真的左孩子而已
	{
		p = p->rchild;
	}
	return p;
}

ThreadNode* PriorNode(ThreadNode* p)
{
	if (p->rtag == 0)
	{
		return Lastnode(p->lchild);
	}
	else
	{
		return p->lchild;
	}
}

利用中序前驱的查找对树进行逆向中序遍历

void Inorder(ThreadNode* T)
{
	for (ThreadNode* p = Lastnode(T); p != NULL; p = PriorNode(p))
	{
		visit_xiansuo(p);
	}
}

对某一个结点进行中序线索化的代码

BiTNode* p;//指向我们要线索化的结点
BiTNode* pre = NULL;//时刻记录当前结点的前驱结点
BiTNode* final = NULL;//找到了就存final里

void visit_clue(BiTNode* T)
{
	if (T == p)
	{
		final = pre;//找到前驱咯
	}
	else
	{
		pre = T;
	}
}

bool mid_clue_tree(BiTree T)
{
	if (T != NULL)
	{
		mid_clue_tree(T->lchild);
		visit_clue(T);
	    mid_clue_tree(T->rchild);
	}
}

对整棵二叉树进行线索化的代码

ThreadNode* pre_mid = NULL;//也可以用引用搞成参数
void visit_clue_all(ThreadNode* T)
{
	if (T->lchild == NULL)
	{
		T->lchild = pre_mid;
		T->ltag = 1;
	}
	else
	{
		T->ltag = 0;
	}

	if (pre_mid != NULL && pre->rchild == NULL)
	{
		pre_mid->rchild = T;//一箭双雕，你的前驱我的后继
		pre_mid->rtag = 1;
	}
	pre_mid = T;
}

bool mid_CreateInThread(ThreadTree T)
{
	pre_mid = NULL;
	if (T != NULL)
	{
		mid_CreateInThread(T->lchild);
		visit_clue_all(T);
		mid_CreateInThread(T->rchild);
		if (pre_mid->rchild == NULL)//对最后一个pre_all做处理
		{
			pre_mid->rtag = 1;
		}
	}
}

2.先序线索二叉树

请添加图片描述

（1）转化方法
1.写出先序遍历的结果
2.根据结果将空链域指向前驱和后驱，实现线索化
（2）先序线索二叉树中先序后继的查找
1.若p->rtag==1;则next=p->rchild;
2.若p->rtag==0;则由于根左右，因此若有左孩子则后继为左孩子，若没有左孩子，则后继为右孩子
（3）先序线索二叉树中先序前驱的查找
1.若p->ltag=1;则prior=p->lchild;
2.若p->ltag=0;则
A.找谁的左孩子是他，则为他的前驱
B.找谁的右孩子是他，这个结点的左孩子最下面（有右则右，没右则左）的结点就是所找的前驱
C.找谁的右孩子是他，但是发现找到的那个结点没有左孩子，则该结点就是所求的前驱结点
D.如果都没有父节点那就不用找了，无论哪种都得从头到尾遍历，或者使用三叉链表

先序线索化

ThreadNode* pre_pre = NULL;
bool pre_CreateInThread(ThreadTree T)
{
	pre_mid = NULL;
	if (T != NULL)
	{
		visit_clue_all(T);
		if (T->ltag == 0)//需要特别注意，因为刚刚对T处理的时候给lchild赋值了
		{
			pre_CreateInThread(T->lchild);
		}
		pre_CreateInThread(T->rchild);
		if (pre_mid->rchild == NULL)//对最后一个pre_all做处理
		{
			pre_mid->rtag = 1;
		}
	}
}

3.后序线索二叉树

请添加图片描述

（1）转化方法
1.写出后序遍历的结果
2.根据结果将空链域指向前驱和后驱，实现线索化
（2）后序线索二叉树中后序后继的查找
1.若p->rtag==1;则next=p->rchild;
2.若p->rtag==0;则
A.若没有父节点则没有后继
B.若有父节点，且他是左孩子，且父节点没有右孩子，则他为所求
C.若有父节点且他是左孩子，且父节点有右孩子，则找最下面的结点（寻找分式：能左则左，没左则右）
D.若有父节点且他是右孩子，则父节点为所求，无论哪种都得从头到尾遍历，或者使用三叉链表
（3）后序线索二叉树中后序前驱的查找
1.若p->rtag==1;则next=p->rchild;
2.若p->rtag==0;则（1）若他有右孩子，则右孩子为所求（2）若他没有右孩子，则左孩子为所求

后序线索化代码

ThreadNode* pre_last = NULL;
bool last_CreateInThread(ThreadTree T)
{
	pre_last = NULL;
	if (T != NULL)
	{
		pre_CreateInThread(T->lchild);
		pre_CreateInThread(T->rchild);
		visit_clue_all(T);
		if (pre_last->rchild == NULL)//对最后一个pre_all做处理
		{
			pre_last->rtag = 1;
		}
	}
}

九、树的存储结构

（1）基于顺序存储的双亲表示法

1. 树的双亲表示法

（1）由于普通树并不像二叉树那样每个结点的分支个数固定，因此没有所谓完全树，也没有办法按照树的结点的下标来判断两个结点之间的关系
（2）因此，如果想要用顺序存储来表示一棵普通树，那就必须开辟一个新的存储单元parent，来存储各个结点的双亲结点（根节点没有父节点，因此设置为-1）

2. 拓展：森林的双亲表示法

森林：m（非负整数）棵互不相交的树的集合
森林的双亲表示法：和普通树一模一样

3.双亲表示法的优缺点

虽然便于查找双亲结点，但是如果想找孩子结点只能遍历整个数组
因此更加适用于多找双亲少找孩子的情况，如：并查集

（2）基于顺序+链式的孩子表示法

1. 普通树的孩子表示法

原理：用数组顺序存储各个结点，例外保存孩子链表的头指针

孩子表示法的结构体定义

struct CTNode {
	int child;//孩子结点在数组中的位置
	struct CTNode* next;//下一个孩子
};
typedef struct {
	int data;
	struct CTNode* firstChild;//第一个孩子
}CTBox;
#define MAX_TREE_SIZE 100
typedef struct {
	CTBox nodes{ MAX_TREE_SIZE };
	int n, r;//结点数和根的位置
}CTree;

2. 拓展：森林的孩子表示法

在这里插入图片描述

3. 孩子表示法的优缺点

便于找孩子，但是若要找父亲则需要遍历数组和链表
因此此类存储方式适合找孩子多，找双亲少的情况，如：服务流程树
服务流程树：向下延申的流程，如：查询话费按1…等等

（3）基于链式存储的孩子兄弟表示法

1. 普通树的孩子兄弟表示法

原理：设置两个指针，一个指向第一个孩子，一个指向右边第一个兄弟

孩子兄弟表示法

typedef struct CSNode {
	int data;
	struct CSNode* firstchild, * nextsibling;//前者指向第一个孩子，后者指向右边第一个兄弟
}CSNode,*CSTree;

普通树

请添加图片描述

孩子兄弟表示对应的存储形式

在这里插入图片描述

2. 森林的孩子兄弟表示法

在这里插入图片描述

十、树、森林、二叉树的转换

（1）树转二叉树

（1）技巧：
A. 先在二叉树中画一个根节点
B.按树的层序依次处理每个结点
C.结点的处理方式：孩子兄弟表示法（个人觉得王道”冰糖葫芦“的说法有点累赘，按照孩子兄弟表示法就挺好的）
普通树
转换完成的二叉树

在这里插入图片描述

（2）森林转二叉树

（1）技巧：
A. 先在二叉树中画一个根节点
B.按森林的层序依次处理每个结点
C.结点的处理方式：孩子兄弟表示法（把森林中每棵树的根节点看作是兄弟结点即可）
转换前的森林

在这里插入图片描述

转化后的二叉树

在这里插入图片描述

（3）二叉树转树

（1）原理：按照刚刚树转二叉树的方式逆转回去即可
转化前的二叉树
转换后的普通树

（4）二叉树转森林

（1）原理：按照刚刚森林转二叉树的方式逆转回去即可
转之前的二叉树
转之后的森林

十一、树和森林的遍历

（1）树的遍历

1. 先根遍历/树的深度优先遍历

逻辑和二叉树的先根遍历一模一样
注意：对普通树的先根遍历和对与该普通树对应的二叉树的先序遍历的相同的

先根遍历伪代码

void tree_preorder(TreeNode* R)
{
	if (R != NULL)
	{
		visit_tree(R);
		while (R还有下一个子树T)
		{
			tree_preorder(T);
		}
	}
}

2. 后根遍历/树的深度优先遍历

逻辑和二叉树的后序遍历一模一样
注意：对普通树的后根遍历和对与该普通树对应的二叉树的后序遍历的相同的

后根遍历伪代码

void tree_postorder(TreeNode* R)
{
	if (R != NULL)
	{
		while (R还有下一个子树T)
		{
			tree_postorder(T);
		}
		visit_tree(R);
	}
}

3. 层序遍历/树的广度优先遍历

实现思路和二叉树的辅助队列法完全一致

（2）森林的遍历

1. 先序遍历

（1）原理（其实就是一棵一棵来）
A. 若森林非空，访问森林的一棵树的根节点
B. 先序遍历第一棵树中根节点的子树森林
C. 先序遍历除去第一棵树之后剩余的树构成的森林
（2）森林的先序遍历和与该森林对应的二叉树的先序遍历结果一致

2. 中序遍历

（1）原理
A. 若森林非空，中序遍历森林中第一棵树的根节点的子树森林
B. 访问第一棵树的根节点
C. 中序遍历森林中其他的树
（2）从效果上这个中序更像后序
（3）那为什么叫中序呢，我想是因为森林的这种遍历和与之对应的二叉树的中序遍历的效果保持一致

十二、哈夫曼树

在这里插入图片描述

（1）带权路径长度

（1）结点的权：有某种现实含义的数值，比如代表着该结点的重要性
【举例】图中的1 2 4 5 这些数字
（2）结点的带权路径长度：从树的根到该结点的路径长度（经过的边树）该结点的权值
【举例】图中绿色叶子结点3的带权路径长度为33=9
（3）树的带权路径长度：树中所有叶子结点的带权路径长度之和（WPL）
【举例】图中树的带权路径长度为：5 * 3 + 1 * 3 + 10 * 3 + 3 * 3 + 1 * 4 = 61

（2）哈夫曼树的定义

在含有n个带权叶子结点的二叉树中，WPL最小的二叉树称为哈夫曼二叉树，也称为最优二叉树

【举例】包含以上四个叶子结点的哈夫曼中的两个如图

（3）哈夫曼树的构造（重点）

对于给定的几个即将称为叶子结点的结点，选取其中权值最小的两个结点，作为左节点和右节点，并得到一个新结点，新结点的权值为左右节点的权值之和
对于新的一堆结点，按照一样的方式进行选取和合并，直到最后合并为一棵树
注意：这只是WPL最小的其中一种哈夫曼树，哈夫曼树不唯一
对于n个原始结点，最终哈夫曼树的结点总数为2n-1
每个初始结点都将称为叶子结点，并且权值越小的结点路径长度越大（也就是能最终WPL最小的原理了）
哈夫曼树中不存在度为1的结点

（4）哈夫曼编码

（1）编码原理：做出哈夫曼树后，从根节点出发，向左为0，向右为1
编码结果：
A—10
B—111
C—0
D—110
神奇的发现：你输入0肯定是C，其他三个都是1开头，然后10就肯定是A，没有101什么的来混淆！！！
也就是说对于一串二进制码的翻译不会发生歧义！！！
这是哈夫曼树的功劳！！！
像下面这个不是哈夫曼就没有这种效果
但是对于不同哈夫曼树编码就不一样
（2）小知识点补充：固定长度编码与可变长度编码
顾名思义即可，传统的是固定，哈夫曼是可变

十二、并查集（Disjoint Set）

（1）如何表示集合关系

并查集的逻辑结构：集合
集合中元素的关系：同属于一个集合或者不属于一个集合
对于集合元素的处理方式：森林也是互不相交的树的集合，因此可以将同一个集合的元素编织成一棵树，将几个不同的集合绘制成一个森林

1. 对于集合常见的操作一：判断一个元素属于哪一个集合（“查”操作）

思路：一直往上找根节点即可

2. 对于集合常见的操作二：判断两个元素是否属于同一个集合

两个都往上找根节点，判断根节点是否一致即可

3. 对于集合常见的操作三：将两个集合合并成一个集合

让一个集合树成为另一个集合树的根节点的一个子节点即可
合并前
合并后

（2）并查集的代码实现

利用双亲表示法实现，便于实现并和查两个操作（存储结构）
具体方式：利用数组即可

初始化并查集

#define SIZE 100
void Initial(int s[])
{
	for (int i = 0; i < SIZE; i++)
	{
		s[i] = -1;
	}
}

查操作的实现

int Find(int s[], int x)
{
	while (s[x] >= 0)
	{
		x = s[x];
	}
	return x;
}
//最坏时间复杂度为O（n）

并操作的实现

void Union(int s[], int Root1, int Root2)
{
	if (Root1 == Root2)
	{
		return;
	}
	s[Root2] = Root1;
}
//时间复杂度为O（1）

（3）并查集的优化

需要优化的地方：查操作的时间复杂度
不难发现：查操作的时间复杂度与查的结点的深度有关，越深时间复杂度越高，换个算法，只要整棵树的高度最小，查操作的效率就会相应的变高
优化的方法：
A. 用根节点的s【】值的绝对子和表示树的结点总数（包括根节点）
B. 在合并时，把小树合并到大树上

并操作的优化

void Union_new(int s[], int Root1, int Root2)
{
	if (Root1 == Root2)
	{
		return;
	}
	if (s[Root1] > s[Root2])
	{
		s[Root1] += s[Root2];
		s[Root2] = Root1;
	}
	else
	{
		s[Root2] += s[Root1];
		s[Root1] = Root2;
	}
}

在这里插入图片描述

以上可以保证n个结点合并后树高不超过：[logn]+1，从而保证时间复杂度为O(logn)
疑惑：结点个数也不能直接决定高度吧，不是要高度最小吗

（4）并查集的终极优化

上面是对union的优化，这里对find也进行优化，也称为：压缩路径
其实并不是对当前寻找的路径优化（确实除了按部就班也没有其他方法），而是以后查找提供了遍历
具体：把我这次查找的结点以及查找过程中路过的结点，都全部接到根节点上，下次就好找了

并查集的终极优化

int Find_new(int s[], int x)
{
	int root = x;
	while (s[root] >= 0)
	{
		root = s[root];
	}
	while (x != root)//压缩路径
	{
		int t = s[x];
		s[x] = root;
		x = t;
	}
	return root;
}

这次优化之后的时间复杂度比O(logn)还小，几乎是常数级的
无论是对并的优化还是对查的优化，目的都是优化树的高度

总结

本章的内容非常的多，花了一个多星期才整理完，代码难度也高了特别多，思想方面倒是还好，还是要多敲代码，解决到时候代码题的困难！

408数据结构第五章 树与二叉树

408数据结构

文章目录

前言

一、树的基本内容

（1）基本概念

1.树的分类

（2）基本术语

1.结点之间的关系描述

2.结点、树的属性描述

3.有序树、无序树

4.森林

二、树的常考性质

三、二叉树

（1）二叉树的分类

（2）二叉树的五种形态

（3）几个特殊的二叉树

1.满二叉树

2.完全二叉树

3.二叉排序树

4.平衡二叉树

四、二叉树的常考性质

五、二叉树的存储结构

六、二叉树的遍历

（1）前序遍历（NLR）

（2）中序遍历（LNR）

（3）后序遍历（LRN）

（4）层次遍历

七、遍历的应用：反推序列

（1）问题一：单独知道一种遍历结果能不能反推序列

（2）问题二：知道哪些遍历结果才能得到唯一的树

1.前序+中序

2.后序+中序

（3）层序+中序

八、线索二叉树

（1）普通二叉树的缺陷–线索二叉树应运而生

（2）线索二叉树

1.中序线索二叉树

2.先序线索二叉树

3.后序线索二叉树

九、树的存储结构

（1）基于顺序存储的双亲表示法

1. 树的双亲表示法

2. 拓展：森林的双亲表示法

3.双亲表示法的优缺点

（2）基于顺序+链式的孩子表示法

1. 普通树的孩子表示法

2. 拓展：森林的孩子表示法

3. 孩子表示法的优缺点

（3）基于链式存储的孩子兄弟表示法

1. 普通树的孩子兄弟表示法

2. 森林的孩子兄弟表示法

十、树、森林、二叉树的转换

（1）树转二叉树

（2）森林转二叉树

（3）二叉树转树

（4）二叉树转森林

十一、树和森林的遍历

（1）树的遍历

1. 先根遍历/树的深度优先遍历

2. 后根遍历/树的深度优先遍历

3. 层序遍历/树的广度优先遍历

（2）森林的遍历

1. 先序遍历

2. 中序遍历

十二、哈夫曼树

（1）带权路径长度

（2）哈夫曼树的定义

（3）哈夫曼树的构造（重点）

（4）哈夫曼编码

十二、并查集（Disjoint Set）

（1）如何表示集合关系

1. 对于集合常见的操作一：判断一个元素属于哪一个集合（“查”操作）

2. 对于集合常见的操作二：判断两个元素是否属于同一个集合

3. 对于集合常见的操作三：将两个集合合并成一个集合

（2）并查集的代码实现

（3）并查集的优化

（4） 并查集的终极优化

总结

网站公告

408数据结构第五章树与二叉树

（4）并查集的终极优化