2.3.哈夫曼树
408数据结构学习笔记——树与二叉树的应用——哈夫曼树和哈夫曼编码、并查集_江南江南江南丶的博客-CSDN博客
1.哈夫曼树的定义：在n个带权叶节点的二叉树中，带权路径长度（从该结点到根节点所经过的边数和该点的权值的乘积）总和最短的树
2.哈夫曼树的构造：每次选择当前权值最低的两个结点合并成一个新的结点（该新结点的权值为被合并的两个结点之和），如此循环直到只剩下一个结点
3.哈夫曼树前缀编码翻译：哈夫曼树的编码可以理解为从根至该字符的路径上边标记的序列，其中变标记为0表示转向左孩子，标记为1表示转向右孩子（也可以0对应右，1对应左）
2.4.并查集
408数据结构学习笔记——树与二叉树的应用——哈夫曼树和哈夫曼编码、并查集_江南江南江南丶的博客-CSDN博客
1.并查集的数据结构定义：采用双亲表示法，数组元素的值即它的双亲结点的数组下标
#define MAXSIZE 100 int UFSets[MAXSIZE];
2.初始化：将每个结点的值设置为-1，表示每个结点都是一颗单独的树，即n个子集
void InitUFSets(int arr[]) { for (int i = 0; i < MAXSIZE; i++) arr[i] = -1; }
2.Find操作：找到该结点的根节点；根节点的值为负数（-1或者绝对值代表这个树的总结点数）
int Find(int arr[], int x) { while (arr[x] >= 0) x = arr[x]; return x; }
3.Union操作：①两个结点都是根节点，直接Union
void Union(int arr[], int root1, int root2) { S[root2] = root1; }
②两个结点是非根节点：先用find找到各自的根节点，再将Union这两个根节点
int Find(int arr[], int x){ //找到x的根节点 while(arr[x] >= 0) x = arr[x]; return x; } void Union(int arr[], int x, int y){ int root1 = Find(arr, x); int root2 = Find(arr, y); arr[root2] = root1; //将root2的双亲结点改为root1 }
4.Union操作的优化：根节点的绝对值代表这个树的总结点个数，小树合并到大树O（log n）
void Union(int arr[], int root1, int root2){ if (arr[root1] < arr[root2]) { //root1为大树，root2为小树 arr[root1] += arr[root2]; //两个树的结点相加 arr[root2] = root1; //root2的双亲结点修改为root1 } else { //root2为大树，root1为小树 arr[root2] += arr[root1]; arr[root1] = root2; } }
5.Find操作的优化（压缩路径）：该结点到根节点路径上的每个结点都挂到根节点上
int Find(int arr[], int x) { int root = x; while (arr[root] >= 0) root = arr[root]; //跟普通find操作一样，先找到根节点 while (arr[x] >= 0) { //逐一修改路径上每个结点的双亲结点为根节点 int temp = x; x = arr[x]; arr[temp] = root; } return root; }
2.5.二叉查找树
408数据结构学习笔记——二叉排序树、二叉平衡树、红黑树_江南江南江南丶的博客-CSDN博客_二叉排序树和红黑树
1.数据结构定义：和普通二叉树的定义一样，只是按左小右大的顺序排列
typedef struct BSTNode{ struct BSTNode *lchild, *rchild; int value; }BSTNode, *BSTree;
2.查找操作：非递归实现更简单
BSTNode* Search(BSTree T,int key){ while (T && key != T->data) { //T当前非空或者当前结点的值不等于key if (key > T->data) T = T->lchild; //key大于当前结点的值，去左子树 else T = T->rchild; //key小于当前结点的值，去右子树 } return T; //返回T所指向的结点，可能是NULL }
3.插入：根据左小右大的原则，逐层找到空结点插入
4.删除：三种情况
①删除叶子结点：直接删除
②删除只有左子树或只有右子树的结点：让其子树的根节点（即被删除结点的左右子树）代替
③删除有左右子树的结点：根据中序遍历的特性，替换成直接前驱或直接后继
planA：替换成直接后继。找到其右子树的最左下的结点替换（最左下即该结点一定没有左孩子），而被替换的结点由它的右子树的根节点代替（转换成2）
planB：替换成直接前驱。找到其左子树的最右下的结点替换（最右下即该结点一定没有右孩子），而被替换的结点由它的左子树的根节点代替（转换成2）
排序二叉树删除叶子结点后重新加入：不会改变树形结构
排序二叉树删除分支结点后重新加入：一定改变树形结构
2.6.平衡二叉树
408数据结构学习笔记——二叉排序树、二叉平衡树、红黑树_江南江南江南丶的博客-CSDN博客_二叉排序树和红黑树
1.数据结构定义：与二叉树相比多一个变量平衡因子
typedef struct AVLTNode{ int value; int banlance; //平衡因子 struct AVLTNode *lchild, *rchild; }AVLTNode, *AVLTree;
2.查找操作：和二叉查找树一致（平衡二叉树是对二叉排序树的优化）
AVLTNode* Search(AVLTree T, int key) { while (T && T->data != key) { if (key > T->data) T = T->lchild; else T =T->rchild; } }
3.插入操作：
①从添加结点往上找，找到最小不平衡子树
②先将LR型→LL型/RL型→RR型
③LL型：右转，中为根
④RR型：左转，中为根
