树
基本概念
树的基本概念
- 树： n n n个结点的有限集（树是一种递归的数据结构，适合于表示具有层次的数据结构）。是递归定义的。
- 根结点：只有子结点没有父结点的结点。除了根结点外，树任何结点都有且仅有一个前驱。
- 分支结点：有子结点也有父结点的结点。
- 叶子结点：没有子结点只有父结点的结点。
- 祖先：根结点到结点的路径上的任意结点都是该结点的祖先。
- 双亲：靠近根结点且最靠近该结点的结点。
- 兄弟：有共同双亲结点的结点。
- 堂兄弟：双亲结点在同一层的结点。
- 空树：结点数为 0 0 0的数。
- 子树：当 n > 1 n>1 n>1时，其余结点可分为 m m m个互不相交的有限集合，每个集合本身又是一棵树，其就是根结点的子树。
- 结点的度：一个结点的孩子（分支）个数。
- 树的度：树中结点的最大度数。
- 结点的层次（深度）：从上往下数。
- 结点的高度：从下往上数。
- 树的高度（深度）：多少层。
- 两结点之间的路径：由两个结点之间所经过的结点序列构成。
- 两结点之间的路径长度：路径上所经过的边的个数。
- 树的路径长度：指树根到每个结点的路径长的总和，根到每个结点的路径长度的最大值是树的高。
- 有序树：树各结点的子树从左至右有次序不能互换。
- 无序树：树各结点的子树从左至右无次序可以互换。
森林的基本概念
- 森林时 m m m棵互不相交的树的集合。
- 一颗树可以被分为森林。
树的性质
- 结点数=总度数 + 1 +1 +1。（加一是因为根结点）
- 树的度 m m m代表至少一个结点度是为 m m m，且一定是非空树，至少有 m + 1 m+1 m+1个结点；而 m m m叉树指所有结点的度都小于等于 m m m，可以是空树。
- 度为 m m m的树以及 m m m叉树第 i i i层至多有 m i − 1 m^{i-1} mi−1个结点。（如完全二叉树）
- 高度为 h h h的 m m m叉树至多有 m h − 1 m − 1 \dfrac{m^h-1}{m-1} m−1mh−1个结点。
- 高度为 h h h的 m m m叉树至少有 h h h个结点，度为 m m m的树至少有 h + m − 1 h+m-1 h+m−1个结点。
- 具有 n n n个结点的 m m m叉树最小高度为 ⌈ log m ( n ( m − 1 ) + 1 ) ⌉ \lceil\log_m(n(m-1)+1)\rceil ⌈logm(n(m−1)+1)⌉。已知高度最小时所有结点都有 m m m个孩子，所以 m h − 1 − 1 m − 1 < n < ⩽ m h − 1 m − 1 \dfrac{m^{h-1}-1}{m-1}<n<\leqslant\dfrac{m^h-1}{m-1} m−1mh−1−1<n<⩽m−1mh−1，从而得到 h − 1 < log m ( n ( m − 1 ) + 1 ) ⩽ h h-1<\log_m(n(m-1)+1)\leqslant h h−1<logm(n(m−1)+1)⩽h。
二叉树
二叉树的基本概念
- 二叉树是 n n n个结点构成的有限集合。
- 二叉树可以为空二叉树，也可以是由一个根结点和两个互不相交的被称为根的左子树和右子树构成。左子树和右子树又分别是一棵二叉树，左右子树不能颠倒。
- 满二叉树：一棵高度为 h h h，含有 2 h − 1 2^h-1 2h−1个结点的二叉树；只有最后一层有叶子结点，不存在度为 1 1 1的结点；按层序从 1 1 1开始编号，结点 i i i的左孩子为 2 i 2i 2i，右孩子为 2 i + 1 2i+1 2i+1，父结点如果有为 ⌊ i 2 ⌋ \lfloor\dfrac{i}{2}\rfloor ⌊2i⌋。
- 完全二叉树：当且仅当其每个结点都与高度 h h h满二叉树编号 1 1 1到 n n n的结点一一对应时该二叉树就是完全二叉树；只有最后两层有叶子结点，最多只有一个度为 1 1 1的结点，即 n 1 = 0 / 1 n_1=0/1 n1=0/1，且一定为左孩子； i ⩽ ⌊ n 2 ⌋ i\leqslant\lfloor\dfrac{n}{2}\rfloor i⩽⌊2n⌋为分支结点， i > ⌊ n 2 ⌋ i>\lfloor\dfrac{n}{2}\rfloor i>⌊2n⌋为叶子结点。
- 二叉排序树：左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字；左右子树又各是一棵二叉排序树。
- 平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过 1 1 1。
二叉树的性质
- 设非空二叉树中度为 0 0 0、 1 1 1和 2 2 2的结点个数分别为 n 0 n_0 n0， n 1 n_1 n1、 n 2 n_2 n2，则 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1（叶子结点比二分结点多一个）。假设树中结点的总数为 n n n，则 n = n 0 + n 1 + n 2 n=n_0+n_1+n_2 n=n0+n1+n2，又根据树的结点等于总度数 + 1 +1 +1得到 n = n 1 + 2 n 2 + 0 n 0 + 1 n=n_1+2n_2+0n_0+1 n=n1+2n2+0n0+1，所以相减就得到结论。
- 二叉树的第 i i i层至多有 2 i − 1 2^{i-1} 2i−1个结点。
- 高度为 h h h的二叉树至多有 m h − 1 m − 1 \dfrac{m^h-1}{m-1} m−1mh−1个结点。
- 具有 n n n个结点的完全二叉树的高度 h = ⌈ log 2 ( n + 1 ) ⌉ h=\lceil\log_2(n+1)\rceil h=⌈log2(n+1)⌉或 ⌊ log 2 n ⌋ + 1 \lfloor\log_2n\rfloor+1 ⌊log2n⌋+1。 2 h − 1 − 1 < n ⩽ 2 h − 1 2^{h-1}-1<n\leqslant2^h-1 2h−1−1<n⩽2h−1。
- 完全二叉树最多只有一个度为 1 1 1的结点，度为 0 0 0度为 2 2 2的结点的个数和一定为奇数；若完全二叉树有 2 k 2k 2k个结点，则必然 n 1 = 1 n_1=1 n1=1， n 0 = k n_0=k n0=k， n 2 = k − 1 n_2=k-1 n2=k−1，若完全二叉树有 2 k − 1 2k-1 2k−1个结点，则必然 n 1 = 0 n_1=0 n1=0， n 0 = k n_0=k n0=k， n 2 = k − 1 n_2=k-1 n2=k−1。
二叉树存储结构
顺序存储
如果是完全二叉树，可以按照顺序进行存储，如果 i i i有左孩子则 2 i ⩽ n 2i\leqslant n 2i⩽n，若有右孩子则 2 i + 1 ⩽ n 2i+1\leqslant n 2i+1⩽n，若有叶子或分支结点则 i > ⌊ n 2 ⌋ i>\lfloor\dfrac{n}{2}\rfloor i>⌊2n⌋。
如果不是完全二叉树，则让二叉树的编号与完全二叉树相对应再存入数组，其他的结点为空，这种存储方法会浪费较多内存，最坏情况下高度为 h h h，且只有 h h h个结点的单支树也需要 2 h − 1 2^h-1 2h−1个存储单元。
这种存储结构需要从下标 1 1 1开始存储，若从 0 0 0开始则不满足父子结点的性质。
链式存储
链式树具有两个分别指向左右子树的指针。
在含有 n n n个结点的二叉链表中，含有 n + 1 n+1 n+1个空链域。
含有 n n n个结点的二叉链表中，链域一共有 2 n 2n 2n个（每个点有两个链域）。对于除了根结点以外的每个点都是有一个父亲结点，所以一共有 n − 1 n-1 n−1个指针指向某个结点，于是形成 n − 1 n-1 n−1个有内容的链域（减 1 1 1即是根结点）所以一共有 2 n − ( n − 1 ) = n + 1 2n-(n-1)=n+1 2n−(n−1)=n+1个链域没有指向任何东西。
如果要保存父结点的位置，可以添加一个父结点指针，从而变成三叉链表。
二叉树遍历
遍历是按照某种次序将所有结点都访问一遍。
顺序遍历
顺序遍历就是深度优先的遍历，分为三种：
- 先序遍历：根左右 N L R NLR NLR。
- 中序遍历：左根右 L N R LNR LNR。
- 后序遍历：左右根 L R N LRN LRN。
根据算算数表达式的分析树的不同先序、中序、后序遍历方式可以得到前缀、中缀、后缀表达式。
若树的高度为 h h h，则时间复杂度为 O ( h ) O(h) O(h)。
递归与非递归
借助栈可以将本来是递归算法的顺序遍历变为非递归方式。
如中序遍历：
- 沿着根的左孩子结点依次入栈，直到左孩子为空。表示找到了最左边的可以输出的结点。
- 栈顶元素出栈并访问。
- 若栈顶元素的右孩子为空，则继续执行步骤二。
- 若栈顶元素的右孩子不为空，则对其右子树执行步骤一。
先序遍历与中序遍历类似，只是第一步就需要访问中间结点。
后序非递归遍历算法的思路：从根结点开始，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，但是此时不能出栈并访问，因为如果其有右子树，还需按相同的规则对其右子树进行处理。直至上述操作进行不下去，若栈顶元素想要出栈被访问，要么右子树为空，要么右子树刚被访问完（此时左子树早已访问完），这样就保证了正确的访问顺序。
层序遍历
层序遍历就是广度优先的遍历。
- 初始化一个辅助队列。
- 根结点入队。
- 若队列非空，则队头结点出队，访问该结点，如果有并将其左右孩子入队。
- 重复步骤三直至队列空。
遍历序列构造二叉树
若只给出一棵二叉树的前/中/后/层序遍历序列中的一种不能唯一确定一棵二叉树。只有给出中序遍历序列才可能推出唯一二叉树，因为无法确定根结点相对于左右结点的位置：
- 前序+中序：
- 后序+中序。
- 层序+中序。
前序+中序
前序：根+左+右；中序：左+根+右。所以根据三个部分对应相同可以推出。
先序遍历的第一个结点一定是二叉树根结点。中序遍历中根结点必然将序列分为两个部分，前一个序列是左子树的中序序列，后一个序列是右子树的中序序列。同理先序序列中子序列的第一个结点就是左右子树的根结点。
根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以对于先序遍历的 n n n个元素，可以确定卡特兰数 1 n + 1 C 2 n n \dfrac{1}{n+1}C_{2n}^n n+11C2nn个二叉树。
后序+中序
后序：左+根+右；中序：左+根+右。所以根据三个部分对应相同可以推出。
层序+中序
层序：根+左根+右根；中序：左+根+右。所以根据根结点和左右子树的根结点来确定。
线索二叉树
对于二叉树的遍历，只能从根结点开始遍历，如果给任意一个结点是无法完成遍历的。一般的二叉树的左右结点是用来表示父子关系，而不能体现遍历关系。
所以我们就想能否保存结点的前驱和后继，从而能减少重复遍历树。因为一棵树很多结点的左右结点可能是空的，那么这些空闲的指针可以不代表左右子树的根结点，而是用来表示当前遍历方法的前驱或后继。当这个指针表示的是前驱或后继就称为线索，指向前驱的就是前驱线索，由左孩子指针担当，指向后继的就是后继线索，由右孩子指针担当。
线索化
线索化就是要遍历一遍二叉树，然后对当前结点进行处理。
为了区分其左右孩子指针是指向什么，要在结点中新建两个 t a g tag tag位，如当 l t a g = 0 ltag=0 ltag=0表示 l c h i l d lchild lchild指向的是左孩子结点，而为 1 1 1表示其指向前驱。
- 确定线索二叉树类型——中序、先序或后序。
- 按照对应遍历规则，确定每个结点访问顺序并写上编号。
- 将 n + 1 n+1 n+1个空链域连上前驱后继。
- 没有前驱或后继就指向
NULL。 - 这种结构称为线索链表。
在先序线索化的时候要注意，由于是根左右的顺序，在访问根结点时候进行线索化可能就会将左孩子结点由指向左孩子变成指向前驱的线索（该结点本来就没有左孩子），然后处理左子树时会跳到这里指向前驱的线索即前一个结点，就会不断在这里循环（程序把前驱当作左孩子不断回撤）。所以在先序遍历二叉树时要根据 l t a g ltag ltag值判断是否是前驱线索再进行遍历左子树。而右孩子结点则不会有这个问题，因为访问顺序必然是左右，所以不管二叉树右孩子结点指向的是右孩子还是后继都是在当前访问结点后应该访问的结点。
而中序线索化和后序线索化都没有这种问题，因为当前结点的前驱在此时按处理顺序都已经处理完了。
同时三种线索化都需要处理最后一个结点，当最后一个结点的右孩子指针为NULL，要
p
r
e
−
>
r
t
a
g
=
1
pre->rtag=1
pre−>rtag=1。
查找前驱后继
如果某结点的左右孩子指针有孩子而不是指向前驱后继，那么怎么找其前驱后继？
- 中序线索二叉树中找到结点
∗
P
*P
∗P的中序后继
n
e
x
t
next
next：
- 若 p p p右孩子指针指向后继： p − > r t a g = = 1 p->rtag==1 p−>rtag==1，则 n e x t = p − > r c h i l d next=p->rchild next=p−>rchild。
- 若 p p p右孩子指针指向右子树根结点： p − > r t a g = = 0 p->rtag==0 p−>rtag==0，则 n e x t = p next=p next=p右子树中最左下结点。
- 所以可以利用线索对二叉树实现非递归的中序遍历。
- 中序线索二叉树中找到结点
∗
P
*P
∗P的中序前驱
p
r
e
pre
pre：
- 若 p p p左孩子指针指向前驱： p − > l t a g = = 1 p->ltag==1 p−>ltag==1，则 p r e = p − > l c h i l d pre=p->lchild pre=p−>lchild。
- 若 p p p左孩子指针指向左子树根结点： p − > l t a g = = 0 p->ltag==0 p−>ltag==0，则 p r e = p pre=p pre=p左子树中的最右下结点。
- 所以可以利用线索对二叉树实现非递归的逆向中序遍历。
- 先序线索二叉树中找到结点
∗
P
*P
∗P的先序后继
n
e
x
t
next
next：
- 若 p p p右孩子指针指向后继： p − > r t a g = = 1 p->rtag==1 p−>rtag==1，则 n e x t = p − > r c h i l d next=p->rchild next=p−>rchild。
- 若 p p p右孩子指针指向右子树根结点： p − > r t a g = = 0 p->rtag==0 p−>rtag==0，如果 p p p有左孩子，则 p − > n e x t = p − > l c h i l d p->next=p->lchild p−>next=p−>lchild，如果 p p p没有左孩子，则肯定有右孩子， p − > n e x t = p − > r c h i l d p->next=p->rchild p−>next=p−>rchild。
- 所以可以利用线索对二叉树实现非递归的先序遍历。
- 先序线索二叉树中找到结点
∗
P
*P
∗P的先序前驱
p
r
e
pre
pre：
- 若 p p p左孩子指针指向前驱： p − > l t a g = = 1 p->ltag==1 p−>ltag==1，则 p r e = p − > l c h i l d pre=p->lchild pre=p−>lchild。
- 若 p p p左孩子指针指向左子树根结点： p − > l t a g = = 0 p->ltag==0 p−>ltag==0，先序遍历中左右子树的根结点只可能是后继，必须向前找。
- 如果没有父结点所以这时候就找不到 p p p的前驱，只能从头开始先序遍历。
- 如果有父结点，则又有四种情况：
- p p p为左孩子，则根据根左右， p p p的父结点为根所以在 p p p的前面， p − > p r e = p − > p a r e n t p->pre=p->parent p−>pre=p−>parent。
- p p p为右孩子，其左兄弟为空，则根据根左右，顺序为根右，所以 p − > p r e = p − > p a r e n t p->pre=p->parent p−>pre=p−>parent。
- p p p为右孩子且有左兄弟，根据根左右， p p p的前驱就是左兄弟子树中最后一个被先序遍历的结点，即在 p p p的左兄弟子树中优先右子树遍历的底部。
- 若 p p p是根结点，则没有先序前驱。
- 后序线索二叉树中找到结点
∗
P
*P
∗P后序后继
n
e
x
t
next
next：
- 若 p p p右孩子指针指向后继： p − > r t a g = = 1 p->rtag==1 p−>rtag==1，则 n e x t = p − > r c h i l d next=p->rchild next=p−>rchild。
- 若 p p p右孩子指针指向右子树根结点： p − > r t a g = = 0 p->rtag==0 p−>rtag==0，则根据左右根顺序，左右孩子结点必然是 p p p的前驱而不可能是后继，所以找不到后序后继。
- 如果没有父结点只能使用从头开始遍历的方式。
- 如果有父结点则又有四种情况：
- p p p为右孩子，根据左右根，所以 p − > n e x t = p − > p a r e n t p->next=p->parent p−>next=p−>parent。
- p p p为左孩子，右孩子为空，根据左右根，所以 p − > n e x t = p − > p a r e n t p->next=p->parent p−>next=p−>parent。
- p p p为左孩子，右孩子非空，根据左右根，所以 p − > n e x t = p->next= p−>next=右兄弟子树中第一个被后序遍历的结点，即右子树优先左兄弟子树遍历的底部。
- 若 p p p是根结点，则没有后序后继。
- 后序线索二叉树中找到结点
∗
P
*P
∗P后序前驱
p
r
e
pre
pre：
- 若 p p p左孩子指针指向前驱： p − > l t a g = = 1 p->ltag==1 p−>ltag==1，则 p r e = p − > l c h i l d pre=p->lchild pre=p−>lchild。
- 若
p
p
p左孩子指针指向左子树根结点：
p
−
>
l
t
a
g
=
=
0
p->ltag==0
p−>ltag==0，则又有两种情况：
- 若 p p p有右孩子，则按照左右根的情况遍历，右在根的前面，所以 p − > p r e = p − > r c h i l d p->pre=p->rchild p−>pre=p−>rchild。
- 若 p p p没有右孩子，按照左根的顺序，则 p − > p r e = p − > l c h i l d p->pre=p->lchild p−>pre=p−>lchild。
树与森林
树的存储结构
- 双亲表示法：是一种顺序存储方式，一般采用一组数组，每个结点中保存指向双亲的伪指针。查找双亲方便，但是查找孩子就只能从头遍历。
- 孩子表示法：是顺序加链式存储方法，顺序存储所有元素，添加一个 f i r s t C h i l d firstChild firstChild域，指向第一个孩子结构体的指针，孩子结构体包括元素位置索引与指向下一个孩子结构体的 n e x t next next指针。寻找孩子比较方便，但是寻寻找双亲需要遍历 n n n个结点 n n n个孩子链表。
- 孩子兄弟表示法：是一种链式存储方式，定义了两个指针，分别指向第一个孩子与右兄弟，类似于二叉树，可以利用二叉树来实现对树的处理。也称为二叉树表示法。可以将树操作转换为二叉树的操作，但是查找双亲麻烦。可以为每个结点设置一个指向双亲的结点。
森林与树的转换
树与森林的转换，树与二叉树的转换都可以使用孩子兄弟表示法来实现，左孩子右兄弟，如果是森林则认为其根结点为兄弟。
树转换为二叉树
树转换为二叉树的规则：每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟，所以对应的二叉树没有右子树。
树转换成二叉树的画法：
- 在兄弟结点之间加一连线。
- 对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉。
- 以树根为轴心，顺时针旋转 45 ° 45° 45°。
森林转换为二叉树
将森林转换为二叉树的规则与树类似。先将森林中的每棵树转换为二叉树，由于任何一棵和树对应的二叉树的右子树必空，若把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当作第一棵二叉树根的右子树，将第三棵树对应的二叉树当作第二棵二叉树根的右子树……以此类推，就可以将森林转换为二叉树。
森林转换成二叉树的画法：
- 将森林中的每棵树转换成相应的二叉树。
- 每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线。
- 以第一棵树的根为轴心顺时针旋转 45 ° 45° 45°。
二叉树转换为森林
二叉树转换为森林的规则：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，故将根的右链断开。二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树，应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止，最后再将每棵二叉树依次转换成树（左边是孩子右边是兄弟还原），就得到了原森林。
树的遍历
- 先根遍历：若树非空，先访问根结点，再依次对每棵子树进行先根遍历。
- 后根遍历：若树非空，先依次对每棵子树进行后根遍历，最后访问根结点。
- 层次遍历：用辅助队列实现：
- 若树非空，根结点入队。
- 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队。
- 重复步骤二直到队列为空。
森林的遍历
先序遍历森林：
- 访问森林中第一棵树的根结点。
- 先序遍历第一棵树中根结点的子树森林。
- 先序遍历除去第一棵树之后剩余的树构成的森林。
如之前图中森林先序遍历为 A B C D E F G H I ABCDEFGHI ABCDEFGHI。
中序遍历森林：
- 先序遍历第一棵树中根结点的子树森林。
- 访问森林中第一棵树的根结点。
- 中序遍历除去第一棵树之后剩余的树构成的森林。
可以把每个树先按序遍历再合在一起，也可以先转换为二叉树再遍历。
如之前图中森林序中遍历为 B C D A F E H I G BCDAFEHIG BCDAFEHIG。
如果通过转换，那么遍历的结果是等价的：
| 树 | 森林 | 二叉树 |
|---|---|---|
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 | 中序遍历 |
转换关系
假设森林为 F F F，树为 T T T，转换而来的二叉树为 B B B。
结点关系
- T T T有 n n n个结点，叶子结点个数为 m m m，则 B B B中无右孩子的结点个数为 n − m + 1 n-m+1 n−m+1个。
树转换为二叉树时，树的每个分支节结点的所有子结点的最右子结点无右孩子，根结点转换后也无右孩子。
- F F F有 n n n个非终端结点，则 B B B中无右孩子的结点有 n + 1 n+1 n+1个。
根据森林与二叉树转换规则“左孩子右兄弟”， B B B中右指针域为空代表该结点没有兄弟结点。森林中每棵树的根结点从第二个开始依次连接到前一棵树的根的右孩子，因此最后一棵树的根结点的右指针为空，这里有一个。另外，每个非终端结点即代表有孩子，其所有孩子结点不论有多少个兄弟，在转换之后，最后一个孩子的右指针一定为空，故树 B B B中右指针域为空的结点有 n + 1 n+1 n+1个。
边关系
- F F F有 n n n条边、 m m m个结点，则 F F F包含 T T T的个数为 m − n m-n m−n。
若有 n n n条边，则如果全部组成最小的树每个需要两个结点，总共需要 2 n 2n 2n个结点，组成 n n n根树。假定 2 n > m 2n>m 2n>m，则还差 2 n − m 2n-m 2n−m个结点才能两两成树，所以少的这些结点不能单独成树，导致有 2 n − m 2n-m 2n−m个结点只能跟其他现成的树组成结点大于二的树。所以此时只能组成 n − ( 2 n − m ) = m − n n-(2n-m)=m-n n−(2n−m)=m−n棵树。
树的应用
哈夫曼树
哈夫曼树的定义
- 路径和路径长度：从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。
- 结点的权：有某种现实含义的数值。
- 结点的带权路径长度：从根到该结点的路径长度（经过边数）与该结点权的乘积称为结点的带权路径长度。
- 树的带权路径长度：树中所有叶子的带权路径长度之和称为树的带权路径长度 W P L = ∑ i = 1 n w i l i WPL=\sum_{i=1}^nw_il_i WPL=∑i=1nwili。
- 哈夫曼树（最优二叉树）：带权路径长度最短的二叉树。不一定是完全二叉树。
- 哈夫曼树不存在度为 1 1 1的结点。
构造哈夫曼树
给定 n n n个权值分别为 w 1 , w 2 ⋯ w n w_1, w_2\cdots w_n w1,w2⋯wn的结点，构造哈夫曼树的算法描述如下：
- 将这 n n n个结点分别作为 n n n棵仅含一个结点的二叉树，构成森林 F F F。
- 构造一个新结点，从 F F F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。默认树较深的在右侧。
- 从 F F F中删除刚才选出的两棵树，同时将新得到的树加入 F F F中。
- 重复步骤二和三，直至 F F F中只剩下一棵树为止。
- 每个初始结点最终都会变成叶子结点，且权值越小到根结点的路径长度越长。
- 哈夫曼树的结点总数为 2 n − 1 2n-1 2n−1。
- 构建哈夫曼树时，都是两个两个合在一起的，所以没有度为一的结点，即 n 1 = 0 n_1=0 n1=0。
- 哈夫曼树不唯一，但是 W P L WPL WPL必然最优。
哈夫曼树适合采用顺序结构：已知叶子结点数 n 0 n_0 n0，且 n 1 = 0 n_1=0 n1=0，则总结点数为 2 n 2 + 1 2n_2+1 2n2+1（或 2 n 0 − 1 2n_0-1 2n0−1），且哈夫曼树构造过程需要不停地修改指针，用链式存储的话很容易造成指针偏移。
哈夫曼编码
哈夫曼编码基于哈夫曼树，利用哈夫曼树对 01 01 01的数据进行编码，来表示不同的数据含义，因为哈夫曼树必然权值最小，所以对于越常使用的编码越短，越少使用的编码越长，所以发送信息的总长度是最小的。
将编码使用次数作为权值构建哈夫曼树，然后根据左 0 0 0右 1 1 1的原则，按根到叶子结点的路径就变成了哈夫曼编码。
哈夫曼编码是可变长度编码，即允许对不同字符用不等长的二进制表示，也是一个前缀编码，没有一个编码是另一个编码的前缀。
同样哈夫曼编码也可以用于压缩。
并查集
将一个集合划分为互不相交的子集。类似森林。
一般用树或森林的双亲表示作为并查集的存储结构，每个子集用一个树表示。
用数组元素的下标表示元素名，用根结点的下标表示子合集名，根节点的双亲结点为负数。
存储结构
如子集 S 1 = { A , B , D , E } S_1=\{A,B,D,E\} S1={A,B,D,E}、 S 2 = { C , H } S_2=\{C,H\} S2={C,H}、 S 3 = { F , G , I } S_3=\{F,G,I\} S3={F,G,I}。
存储结构为：
| 数据元素 | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|
| 数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 双亲 | -4 | 0 | -2 | 0 | 3 | -3 | 5 | 2 | 5 |
其中为负数表示这个点有子结点，其绝对值为孩子数量，为正数表示其父结点的索引值。
查找
查找两个元素是否属于同一个集合。
判断两个元素是否属于同一集合只需要找到其根节点进行比较。需要通过递归的方式不断查找父结点。
查的时间复杂度为 O ( n ) O(n) O(n)
合并
如果两个元素不属于同一个集合，且所在的两个集合互不相交，则合并这两个集合。
并的时间复杂度为 O ( 1 ) O(1) O(1)。
路径压缩
用于提高并查集效率。
如果一个结点只有一个子结点，且子结点也只有一个子结点，那么这条链路会非常长，即对应的树的树高会很大，影响查询效率。
所以把沿途的结点的父结点都设为最上面的根节点即可，不用一层层查询了。
按秩合并
并查集经过路径压缩优化之后，并查集并不是是只有两层的一颗树。因为路径压缩只在查找的时候进行，也只压缩一条路径，所有并查集的最终结构仍然可能是比较复杂的。
在将一个新元素并入并查集前，就应该使用按秩合并的方式对并查集进行优化。
为了避免加深树高，所以新的结点应该合并到矮的子树上。
为了降低树的结点数和合并操作的难度，应该将简单的树合并到复杂的树上。
用秩数组来记录每个根结点对应的树的深度（如果不是根结点，则秩数组中的元素大小表示的是以当前结点作为根结点的子树的深度）；一开始，把所有元素的秩值设为1，即自己就为一颗树，且深度为1；合并的时候，比较两个根结点，把秩值较小者合并到较大者中去。
应用
- 判断图的连通分量数—遍历各边，有边相连的两个顶点确认连通，“并”为同一个集合。只要是相互连通的顶点都会被合并到同一个子集合中，相互不连通的顶点一定在不同的子集合中。
-
K
r
u
s
k
a
l
Kruskal
Kruskal算法的最小生成树–各边按权值递增排序，依次处理：判断是否加入一条边之前，先查找这条边关联的两个顶点是否属于同一个集合（即判断加入这条边之后是否形成回郡），若形成回路，则继续判断下一条边；若不形成回路，则将该边和边对应的顶点加入最小生成树
T
T
T，并继续判断
下一条边，直到所有顶点都已加入最小生成树 T T T。