线索二叉树

线索二叉树的基本概念

为了解决无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题， 出现了线索二叉树。
一个二叉树通过如下的方法“穿起来” ： 所有原本为空的右(孩子)指针改为指向该节点在某种遍历序列中的后继， 所有原本为空的左(孩子)指针改为指向该节点的某种遍历序列的前驱。
如图所示：

节点结构

其中 ltag/rtag 为 0 表示 lchild/rchild 指向左/右孩子。
ltag/rtag 为 1 表示 lchild/rchild 指向前驱/后继节点。

几种线索二叉树

先序线索二叉树的特点
节点若无左子树， 则指向先序遍历序列的前驱节点；
节点若无右子树， 则指向先序遍历序列的后继节点。

中序线索二叉树的特点
节点若无左子树， 则指向中序遍历序列的前驱节点；
节点若无右子树， 则指向中序遍历序列的后继节点。

后序线索二叉树的特点
节点若无左子树， 则指向后序遍历序列的前驱节点；
节点若无右子树， 则指向后序遍历序列的后继节点。

树与森林

树的存储结构

双亲表示法

优点： 可以快速的找到结点的双亲结点
缺点： 无法快速找到某个结点的孩子结点， 需要遍历整个表。

孩子表示法

优点： 可以快速的找到某个结点的孩子结点
缺点： 无法快速的找到某个节点的双亲结点

孩子兄弟表示法

优点： 可以方便的实现树与二叉树的相互转化， 可以快速的找到某个结点的孩子。
缺点： 当前的结构下查找双亲结点较麻烦。

树、 森林、 二叉树的转化

树转二叉树

第一步

第二步

第三步

二叉树转树(根节点无右孩子)

第一步
将所有结点的右指针旋转为“横线”

第二步

二叉树转森林（根节点有右孩子）

第一步

第二步

第三步

树和森林的遍历

树的遍历

先序遍历： 先访问根节点， 再按先序访问根节点的每根子树
后序遍历： 先后序访问子树， 最后再访问根节点

先序遍历序列： ABEFCDGHI
后序遍历序列： EFBCGHIDA

森林的遍历

先序遍历： 首先先序遍历第一棵树， 再依次先序遍历剩下的树
后序遍历： 首先后序遍历第一棵树， 再依次后序遍历剩下的树

先序遍历序列： ABDECFG
后序遍历序列： DBEAFCG

并查集

定义

并查集是一种树型的数据结构， 用于处理一些不相交集合（disjoint sets） 的合并及查询问题（即所谓的并、 查） 。 常常在使用中以森林来表示。

init()函数的定义与实现

初始化函数， 定义一个集合数组， 数组长度由题意而定， 将集合中的每一个元素初始化为只有一个单元素的集合。

Find()函数的定义与实现

Merge()函数的定义与实现

路径压缩

并查集总结

1. 用集合中的某个元素来代表这个集合， 则该元素称为此集合的代表元；
2. 一个集合内的所有元素组织成以代表元为根的树形结构；
3. 对于每一个元素 x， pre[x] 存放 x 在树形结构中的父亲节点(如果 x 是根节点，则令 pre[x] = x)；
4. 对于查找操作， 假设需要确定 x 所在的的集合， 也就是确定集合的代表元。 可以沿着 pre[x]不断在树形结构中向上移动， 直到到达根节点。

因此， 基于这样的特性， 并查集的主要用途有以下两点：

1. 维护无向图的连通性(判断两个点是否在同一连通块内， 或增加一条边后是否会产生环)；
2. 用在求解最小生成树的 Kruskal 算法

二叉排序树（BST）

定义二叉排序树（BST） 也称为二叉查找树。 二叉排序树或者是一颗空树， 或者是一颗 具有下列特性的非空二叉树：

1. 若左子树非空， 则左子树上所有结点关键字值均小于根结点的关键字值；
2. 右子树非空， 则右子树上所有结点关键字值均大于根结点的关键字值；
3. 左、 右子树本身也分别是一颗二叉排序树
   二叉排序树也是个递归的数据结构： 由二叉排序树的定义可知， 左子树结点值 < 根节点值 < 右子树结点值， 故二叉排序树的中序遍历序列是一个递增有序序列
   

上图二叉排序树的中序遍历序列为： 2 4 5 6 8 9 10 12

存储结构

二叉排序树的存储结构同二叉树的存储结构， 多采用链式存储结构。

typedef struct BiTNodeint key;                  //数据域struct BiTNode *lchild;    //左孩子指针struct BiTNode *rchild;    //右孩子指针
}BiTNode,*BiTree;

二叉排序树的查找

因为二叉排序树有序， 所以查找思想比较简单， 从根结点开始查找， 若树非空， 将 给定值与根结点关键字值比较， 若相等， 则查找成功； 若不等且给定值小于根结点关键 字值， 在根结点左子树中查找； 否则在根结点的右子树查找。 显然这是一个递归的过程。

查找效率

二叉排序树的平均查找长度（ASL） 取决于树的高度， 相同的关键字， 其插入的顺序不同可能形成不同的二叉排序树。 最坏的情况下， 构造二叉树的输入序列是有序的， 形成单支树， 则平均查找长度和单链表相同为 O(n)；最好的情况为二叉平衡树（二叉排序树的左、 右子树的高度之差绝对值不超过 1） ， 它的平均查找长度为 O(log2n);

二叉排序树的插入

插入的新结点一定是某个叶结点
若二叉排序树为空， 则直接插入结点； 若二叉排序树非空， 当值小于根结点时， 插 入左子树； 当值大于根结点时， 插入右子树； 当值等于根结点时不进行插入。
所以二叉排序树的插入就是在是查找过程中， 当树中不存在关键字值等于给定值的 结点时再进行插入的。

int BST_Insert(BiTree &T, KeyType k) 
{//在二叉排序树T中插入一个关键字为k的结点 if（T == NULL)     //原树为空，新插入的记录为根结点{T =(BiTree)malloc(sizeof(BSTNode)); T->key-k;T->lchild = T->rchild = NULL;return 1;     //返回1，表示成功}else if(k == T->key)  //树中存在相同关键字的结点return 0;else if(k < T->key)return BST_Insert(T->lchild, k);   //插入T的左子树elsereturn BST_Insert(T->rchild, k);   //插入T的右子树
}

二叉排序树的构造

构造一棵二叉排序树就是一次输入数据元素， 并将它们插入到二叉排序树中的适合 位置上。 读入一个元素并建立结点， 若二叉排序树为空，将其作为根节点； 若二叉排序 树非空， 当值小于根结点时， 插入左子树；当值大于根结点时， 插入右子树； 当值等于 根结点时， 不进行插入。

void Creat_BST(BiTree &T, KeyType str[], int n)
{//用关键字数组str[]建立一个二叉排序树T = NULL;      //初始时bt为空树int i = 0; while(i < n)   //依次将每个元素插入{BST Insert(T, str[i]); i++;}
}

二叉排序树的删除

在二叉排序树中删除一个关键字时， 不能把该关键字所在的结点为根的子树全部删 除， 而是只删除这一个结点， 并保持二叉排序树的性质。

删除操作的实现过程按 3 种情况来处理：

1. 若被删除结点 p 是叶结点， 则直接删除， 不会破坏二叉排序树的性质；
2. 如果被删除结点 p 只有一颗左子树或右子树， 则让 p 的子树称为 p 父结点的 子树， 替代 p 的位置；
3. 如果被删除结点 p 既有左子树又有右子树， 则令 p 的直接后继(或直接前驱)， 替代 p， 然后从二叉排序树种删除这个直接后继（或直接前驱） ， 这样就转换成课第一或第二种情况。
   

10 是叶结点， 直接删除即可

9 左子树空， 用右子树填补即可

左、 右子树均不空， 在中序序列中找到 4 的直接后继 5， 替代删除 4 即可

在二叉排序树种删除并插入相同结点后， 得到的二叉排序树与原来不一定相同

平衡二叉树（AVL）

定义

平衡二叉树又称 AVL 树， 是一种特殊的二叉排序树， 其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过 1。 平衡因子： 结点左子树和右子树的高度差， 平衡二叉树结点的平衡因子的值只可能为-1， 0， 1。 平衡树的引入也是为了解决二叉排序树单支树查找效率低下而引入的。

重要推论

1. 高度为h的最小平衡二叉树的节点数为N_h，显然N_0=0，N_1=1，N_2=2, 可以证明N_h=N_{h-1}+N_{h-2}+1
2. 含有n个结点的平衡二叉树的最大深度为O（log_{2}n）.平衡二叉树的平均查找长度为O(log_{2}n)

平衡二叉树的建立

每当在二叉排序树中插入（或删除） 一个结点时， 首先检查其插入路径上的结点是否因为此次操作而导致了不平衡， 如果导致了不平衡， 则先找到插入路径上离插入结点 最近的平衡因子绝对值大于 1 的结点 P， 对以 P 为根的子树， 在保持二叉排序树的前提下， 调整各结点的位置关系， 使之重新达到平衡。

平衡二叉树的调整

1. LL 平衡旋转（右单旋转） ： 由于在结点 A 的左孩子（L） 的左子树（L） 上插 入了新结点， 使 A 的平衡因子由 1 增至 2， 导致以 A 为根的子树失去平衡， 需要一次 向右的旋转操作。 将 A 的左孩子 B 向右上旋转代替 A 成为根结点， 将 A 结点向右下旋 转称为 B 的右子树的根节点，而 B 的原右子树则作为 A 结点的左子树。
   

2. RR 平衡旋转（左单旋转） ： 由于在结点 A 的右孩子（R） 的右子树（R） 上 插入了新结点， 使 A 的平衡因子由-1 减至-2， 导致以 A 为根的子树失去平衡， 需要一 次向左的旋转操作。 将 A 的右孩子 C 向左上旋转代替 A 成为根结点， 将 A 结点向左下 旋转称为 C 的左子树的根节点，而 C 的原左子树则作为 A 结点的右子树
   

3. LR 平衡旋转（先左后右双旋转） ： 由于在结点 A 的左孩子（L）的右子树（R） 上插入了新结点， 使 A 的平衡因子由 1 增至 2， 导致以 A 为根的子树失去平衡， 需要进行两次旋转操作， 先左旋转后右旋转。 先将 A 的左孩子 B 的右子树的根节点 E 向左 旋转提升至 B 的位置， 然后再把该 E 结点向右上旋转提升至 A 结点的位置。
   

4. RL 平衡旋转（先右后左双旋转） ： 由于在结点 A 的右孩子（R）的左子树（L） 上插入了新结点， 使 A 的平衡因子由-1 减至-2， 导致以 A 为根的子树失去平衡， 需要 两次旋转操作， 先右旋转后左旋转。 先将 A 结点的右孩子 C 的左子树根节点 D 向右上 旋转提升到 C 结点的位置， 然后再把该 D 结点向左上旋转提升到 A 结点的位置
   

5. 删除操作导致AVL发生不平衡时， 类型判断与插入操作类似。

3+4重构法调整平衡二叉树

任意一棵平衡二叉树， 在进行插入或删除操作之前都应该是一棵平衡二叉树。
在进行插入删除操作之后， 若产生了不平衡情况， 不平衡结点一定位于该结点以上的祖
先节点。
任何一个需要被重平衡的结点都包含了两个子树。

哈夫曼树

路径和路径长度

若在一棵树中存在着一个结点序列 k1， k2， ……， kj， 使得 ki 是 ki+1 的双亲（1<=i<j） ， 则称此结点序列是从 k1 到 kj 的路径。 从 k1 到 kj 所经过的分支数称为这两点之间的路径长度， 它等于路径上的结点数减 1.。

结点的权和带权路径长度在许多应用中， 常常将树中的结点赋予一个有着某种意义的实数， 我们称此实数为该结点的权。 结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。

树的带权路径长度

树中所有叶结点的带权路径长度之和，记为
$$WPL=\sum _{i=1}^n{W}_i\ast l_i$$其中$w_i$是第i个叶结点所带的权值，$l_i$是该叶结点到根结点的路径长度。

哈夫曼树

含有 N 个带权叶子结点的二叉树中， 带权路径长度（WPL） 最小的二叉树， 也称为最优二叉树

哈夫曼树的构造

给定 N 个权值分别为 W1, W2, … , Wn的结点， 通过哈夫曼算法即可得到哈夫曼树：

1. 将这 N 个结点分别作为 N 棵仅含一个结点的二叉树， 构造成森林 F
2. 构造一个新结点， 并从 F 中选取两棵根节点权值最小的树作为新结点的左、 右 子树， 并且将新结点的权值置为左、 右子树上根节点的权值之和
3. 从 F 中删除刚才选出的两棵树， 同时将新得到的树加入到 F 中
4. 重复步骤 2 和 3 ， 直至 F 中只剩下一棵树为止
   

哈夫曼树的性质

1. 每个初始结点最终都会成为叶结点， 并且权值越小的结点到根结点的路径长度越大。
2. 构造过程中共新建了 N-1 个结点（双分支结点） ， 因此哈夫曼树中结点总数 为 2N-1。
3. 每次构造都选择两棵树作为新结点的孩子， 因此哈夫曼树种不存在度为 1 的结点
4. 哈夫曼树的WPL等于分支节点的权值之和

哈夫曼编码

编码的原则

解码的结果唯一、 发送的二进制编码尽可能短

固定长度编码

对于待处理的一个字符串序列， 对每个字符用同样长度的二进制位来表示。

可变长度编码

对不同字符用不等长的二进制为表示， 其可以缩短字符平均编码长度， 压缩数据

前缀编码

没有一个编码是另一个编码的前缀， 可以有效的进行解码

哈夫曼编码

将每个出现的字符当作一个独立的结点， 其权值为它出现的次数，构造出对应的哈夫曼树。 所有的字符结点出现在叶结点中， 可将字符的编码解释为从根至该字符的路径上边标记的序列， 一般来说， 其中边标记为 0 表示“转向左孩子” ， 边标记为 1 表示“转 向右孩子” 。 从树根结点到每个叶子结点的路径上， 所经分支的 0、 1 编码序列等于该叶子结点的二进制编码。

哈夫曼编码的特点

1. 由于根通往任意叶子结点的路径都是不可能是通往其余叶子结点路径的子路径， 因此任意编码串必然为前缀码。
2. 哈夫曼树的特点出现次数越多的字符编码越短， 最终使得整个字符串被编码后的前缀码长度最短， 因此哈夫曼编码产生的是最短前缀码。
3. 同一组结点， 构造出来的哈夫曼树可能不是唯一的， 哈夫曼编码也不一定唯一

k叉哈夫曼树

哈夫曼树只有度为0和度为2的结点， 同理k叉哈夫曼树也只有度为0和度为k的结点。

【例题】一棵k叉哈夫曼树，叶子结点和非叶子结点应满足怎样的关系？

1. 哈夫曼树只有度为0和度为2的结点，同理k叉哈夫曼树也只有度为0 和度为k的结点。
2. 已知树有此性质：n= n_0+ n_k =kn_k+1
3. 故k叉哈夫曼树的叶子结点和非叶子结点应满足n_k= ceil(n0-1/(k-1))
4. 可能要补充虚结点;