③其他操作即main函数
1. void FindNode(BTnode *root, BTDatatype x) //找到待删除的节点 2. { 3. if (root == NULL) 4. return; 5. else 6. { 7. if (x < root->data) 8. { 9. return FindNode(root->left, x); //递归 10. } 11. 12. else if (x > root->data) 13. { 14. return FindNode(root->right, x); //递归 15. } 16. 17. else if (x == root->data) 18. { 19. Del(root); 20. } 21. } 22. } 23. 24. void In_Order(BTnode *root) //中序 25. { 26. if (root == NULL) 27. { 28. printf("NULL "); 29. return; 30. } 31. 32. In_Order(root->left); 33. printf("%d ", root->data); 34. In_Order(root->right); 35. } 36. 37. int main() 38. { 39. BTnode* A = (BTnode*)malloc(sizeof(BTnode)); 40. A->data = 10; 41. A->left = NULL; 42. A->right = NULL; 43. 44. /*BTnode* B = (BTnode*)malloc(sizeof(BTnode)); 45. B->data = 8; 46. B->left = NULL; 47. B->right = NULL; 48. 49. BTnode* C = (BTnode*)malloc(sizeof(BTnode)); 50. C->data = 14; 51. C->left = NULL; 52. C->right = NULL; 53. 54. BTnode* D = (BTnode*)malloc(sizeof(BTnode)); 55. D->data = 7; 56. D->left = NULL; 57. D->right = NULL; 58. 59. BTnode* E = (BTnode*)malloc(sizeof(BTnode)); 60. E->data = 9; 61. E->left = NULL; 62. E->right = NULL; 63. 64. A->left = B; 65. A->right = C; 66. B->left = D; 67. B->right = E; 68. C->left = NULL; 69. C->right = NULL; 70. D->left = NULL; 71. D->right = NULL; 72. E->left = NULL; 73. E->right = NULL;*/ 74. 75. Push(&A, 12); 76. Push(&A, 4); 77. Push(&A, 3); 78. Push(&A, 2); 79. Push(&A, 1); 80. Push(&A, 5); 81. FindNode(A,4); 82. In_Order(A); 83. 84. return 0; 85. }
二叉排序树有一个不好的问题，就是比如插入1 2 3 4 5 6，那我没吃插入都要遍历之前全部的数据，也就是说在某些条件下二叉排序树效率低，这就引出了二叉平衡术来解决这个问题。
7.二叉平衡树（AVL树）
二叉平衡树是为了解决某些特殊情况下二叉排序树效率低下的问题（比如斜树），二叉排序树查找的效率取决于树的高度，所以二叉平衡树会较好的控制树的高度，但相反的二叉平衡树是通过牺牲插入和删除的效率去实现查找效率的提升。
二叉平衡树性质：1、可以是空树 2、任意一个节点的左右子树高度之差不超过1（叶子节点高度为0）
二叉平衡树对于二叉排序树，主要是在插入和删除上增加了一些控制平衡的操作去使任意一个节点的左右子树高度之差不超过1，高度具体是什么意思？
如上图，叶子节点的高度为0，而非叶子节点的高度是他左右子树的最大值+1。AVL树的代码和逻辑相对于之前难度会有一点的上升，这里我就不以插入删除等顺序来讲述，而是按照改进二叉排序树的顺序来写。
以下是他的抽象数据类型，这里比二叉排序树多了一个height来记录当前节点的高度
key 数据域 left 左子树 right 右子树 height 当前节点高度
1. typedef struct Node { 2. int key;//数据域 3. struct Node* left; 4. struct Node* right; 5. int height;//存储当前结点的高度 6. }avlnode, *avltree;
下面所有插入的数据将不会有key相同的情况，因为这会让代码变得复杂，如有这方面的需求自行进行修改。
①调节平衡
我们先不用管怎么判断是否调节平衡的代码怎么写，我先说调节平衡的操作。以下的操作都是对于失衡节点的操作（失衡节点：左子树高度减右子树高度的绝对值大于1的）
这里先写两个后面会用到的宏，意思很简单就不多介绍了。
1. #define HEIGHT(node) ((node==NULL) ? 0 : (((avlnode*)(node))->height)) 2. #define MAX(a,b) ((a) > (b) ? (a) : (b)) 3. 4. int getNode_height(avlnode* node) 5. { 6. return HEIGHT(node); 7. }
第一种：左子树的左节点过高（LL）
由图可知现在的失衡节点是根节点，我们只需对失衡节点右旋就可以解决现在的失衡情况，那具体怎么执行右旋操作呢？以这张图为例，二的右子树更新为3，而2原来的右子树更新为3的左子树，最后通过返回节点的方法替换原来的失衡节点在其父节点位置的指针。
这里我们可以发现此树已经变成一个平衡的树了，并且如果原来的树是按照二叉排序树的规则插入的话，旋转之后的树也是遵循二叉排序树的规则的。代码如下。
1. //LL 左子树的左子树 2. avltree left_left_rotation(avltree tree) 3. { 4. avlnode* k2 = tree->left; 5. tree->left = k2->right; 6. k2->right = tree; 7. //所有的旋转操作重新调整树的高度 8. tree->height = MAX(getNode_height(tree->left), getNode_height(tree->right)) + 1; 9. k2->height = MAX(getNode_height(tree->left), getNode_height(tree->right)) + 1; 10. return k2; 11. }
这里的还一个难点就是如何去确定每一个节点的高度，总体的思路是每个节点自下往上分别+1，而叶子节点高度为0 ，这样我们在确定一个树的节点时只需要知道他子节点的最大高度并+1就好
第二种：右子树的右节点过高（RR）
这与第一种情况非常的相似，以这张图为例，失衡节点为根节点1，我们对其进行左旋操作，把1的右子树更新为1右子树的左子树2，把3的左子树更新为1，最后通过返回节点的方法替换原来的失衡节点在其父节点位置的指针。
原来的树是符合二叉排序树逻辑的，所以这里旋转之后的树也是符合二叉排序树的。代码如下
1. //RR 右子树的右子树 2. avltree right_right_rotation(avltree tree) 3. { 4. avlnode* k2 = tree->right; 5. tree->right = k2->left; 6. k2->left = tree; 7. //所有的旋转操作重新调整树的高度 8. tree->height = MAX(getNode_height(tree->left), getNode_height(tree->right)) + 1; 9. k2->height = MAX(getNode_height(tree->left), getNode_height(tree->right)) + 1; 10. return k2; 11. }
第三种：左子树的右节点过高（LR）
虽然都是左子树导致的失衡，但是我们可以发现这个树通过对失衡节点的右旋没有办法使树平衡，这里直接讲操作，对失衡节点的左子树先进行左旋，再对失衡节点进行右旋就能完成操作
代码如下
1. avltree left_right_rotation(avltree tree) 2. { 3. tree->left = right_right_rotation(tree->left); 4. tree = left_left_rotation(tree); 5. //所有的旋转操作重新调整树的高度 6. return tree; 7. }
第四种：右子树的左节点过高
理解了第三种情况那这个与第三种很相似，对失衡节点的右子树先进行右旋，再对失衡节点进行左旋就能完成操作，代码如下。
1. //RL 右孩子的左子树 2. avltree right_left_rotation(avltree tree) 3. { 4. tree->right = left_left_rotation(tree->right); 5. tree = right_right_rotation(tree); 6. //所有的旋转操作重新调整树的高度 7. return tree; 8. }
②插入操作
插入的逻辑与二叉排序树一样，不一样的是在于如何检测插入是否造成失衡并调整失衡。这里我选择用递归去寻找插入的位置，在递归返回阶段自下而上改变插入位置以上的节点的高度，并检验经过的节点是否失衡，检验方法是子节点之差是否等于2，检测出失衡时再有上面的调节平衡操作来调节。
如上图，我们向往里面插入一个3，那么操作完成之后便如下
这时候我们通过递归可以检测出（代码在下面）根节点4为失衡节点，处理方法为调节平衡里的情况四（LR），具体的插入代码如下。
1. //创建结点的方法 2. avlnode* create_node(int key, avlnode* left, avlnode* right) { 3. avlnode* node = (avlnode*)malloc(sizeof(avlnode)); 4. //记得做判断 5. node->key = key; 6. node->left = left; 7. node->right = right; 8. node->height = 0; 9. return node; 10. } 11. 12. avltree avltree_insertNode(avltree tree, int key) 13. { 14. if (tree == NULL) 15. { 16. avlnode* node = create_node(key, NULL, NULL); 17. tree = node; 18. } 19. else if (key < tree->key)//在左子树中插入结点 20. { 21. //递归寻找插入结点的位置 22. tree->left = avltree_insertNode(tree->left, key); 23. //插入引起的二叉树失衡 24. if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2) 25. { 26. if (key < tree->left->key) 27. { 28. tree = left_left_rotation(tree); 29. } 30. else 31. { 32. tree = left_right_rotation(tree); 33. } 34. } 35. 36. } 37. else if (key > tree->key) 38. { 39. //递归寻找插入结点的位置 40. tree->right = avltree_insertNode(tree->right, key); 41. //插入引起的二叉树失衡 42. if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2) 43. { 44. if (key < tree->right->key) 45. { 46. tree = right_left_rotation(tree); 47. } 48. else 49. { 50. tree = right_right_rotation(tree); 51. } 52. } 53. } 54. 55. //重新调整二叉树的深度 56. tree->height = MAX(getNode_height(tree->left), getNode_height(tree->right)) + 1; 57. 58. return tree; 59. 60. }
③删除操作
删除操作通过传入根节点和想删除的值来实现，删除我同样通过递归来实现，如果想判断想删除的这个值存不存在的话可以另外写一个函数判断一下，代码如下。
1. avlnode* search_node(avltree tree, int key) 2. { 3. if (tree == NULL || tree->key == key) 4. { 5. return tree; 6. } 7. else if (key < tree -> key) 8. { 9. search_node(tree->left, key); 10. } 11. else { 12. search_node(tree->right, key); 13. } 14. }
上面这个函数返回的结果判断是不是NULL，就能表示要删除的这个值存不存在。下面就可以进行主要的删除步骤。先通过递归我们可以找到要被删除的节点，找到节点删除的时候我们面临着二叉树删除的两种情况，被删除的节点有两个子树和被删除节点有一个或没有子树：如果只有一个子树或者没有子树时，我们只需要把子树覆盖被删除节点的位置就行，这一点与之前二叉树的删除一样，但是如果有两个子树，我们不光要像之前找到可以替换被删除的节点（具体看之前二叉树的删除），还要再写一步把用来替换现在删除节点的节点删除的操作，因为我们递归返回时要更新所有节点的高度，所以我们要把最底下改动过位置的节点当成新的删除节点。（这里用画图不能很好的解释，等下具体操作看代码）
遍历返回的时候我们要做两步操作，第一是检测是否失衡，第二是更新当前节点的高度，第二个比较简单我主要解释第一个。删除的检测平衡和添加的不同，删除的失衡节点不好定位，添加在哪那就高，但是删除不能知道哪个高，这也是这里我选择递归寻找失衡节点的原因。首先和插入一样，我们用 if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2) 寻找失衡节点，这里以在左子树删除为例子，那么一定是右子树偏高，那是用RR还是RL呢？如果要用RL就是右子树的左子树导致的失衡（但是对右子树的右子树失衡也能用RL，不理解用手画一下），而RR是右子树的右子树，比较暴力的方法就是直接判断右子树的左子树存不存在时，就肯定可以用RR，其他的情况都有RL。当然也可以继续优化，在判定存在右子树的左子树之后， if (HEIGHT(tree->right->left) - HEIGHT(tree->left) == 1) 就一定用RL，其他情况RR。下面代码用暴力一点的方法。
1. avlnode* search_node(avltree tree, int key) 2. { 3. if (tree == NULL || tree->key == key) 4. { 5. return tree; 6. } 7. else if (key < tree->key) 8. { 9. search_node(tree->left, key); 10. } 11. else { 12. search_node(tree->right, key); 13. } 14. } 15. 16. //寻找最小值 17. avlnode* mininum_node(avltree tree) 18. { 19. if (tree == NULL) 20. { 21. return NULL; 22. } 23. while (tree->right) 24. { 25. tree = tree->right; 26. } 27. return tree; 28. } 29. 30. avltree avltree_deleteNode(avltree tree, int key) 31. { 32. avlnode* node = search_node(tree, key); 33. if (tree == NULL || node == NULL) 34. { 35. return tree; 36. } 37. 38. if (key < tree->key)//要删除的结点在左子树 39. { 40. tree->left = avltree_deleteNode(tree->left, key); 41. if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2) 42. { 43. if (tree->right->left) 44. { 45. tree = right_left_rotation(tree); 46. } 47. else 48. { 49. tree = right_right_rotation(tree); 50. } 51. } 52. } 53. else if (key > tree->key) 54. { 55. tree->right = avltree_deleteNode(tree->right, key); 56. if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2) 57. { 58. if (tree->left->left) 59. { 60. tree = left_left_rotation(tree); 61. } 62. else 63. { 64. tree = left_right_rotation(tree); 65. } 66. } 67. } 68. else//找到待删除的结点 69. { 70. if (tree->left && tree->right) 71. { 72. avlnode* min_node = mininum_node(tree->left); 73. tree->key = min_node->key; 74. tree->left = avltree_deleteNode(tree->left, min_node->key); 75. } 76. else 77. { 78. tree = tree->left ? tree->left : tree->right;//独子 或者无子的情况 79. } 80. } 81. 82. if (tree) 83. { 84. tree->height = MAX(getNode_height(tree->left), getNode_height(tree->right)) + 1; 85. } 86. 87. return tree; 88. }
④其他操作
下面放一些遍历等测试函数
1. #include<stdio.h> 2. #include<stdlib.h> 3. 4. void pre_order(avltree tree) 5. { 6. if (tree) 7. { 8. printf("%d ", tree->key); 9. pre_order(tree->left); 10. pre_order(tree->right); 11. } 12. } 13. 14. void order(avltree tree) 15. { 16. if (tree) 17. { 18. 19. order(tree->left); 20. printf("%d ", tree->key); 21. order(tree->right); 22. } 23. } 24. 25. int main() 26. { 27. avltree tree = NULL; 28. int a[] = { 12,9,17,6,11,13,18,4,15 }; 29. int lenght = sizeof(a) / sizeof(a[0]); 30. for (int i = 0; i < lenght; i++) 31. { 32. tree = avltree_insertNode(tree, a[i]); 33. } 34. 35. pre_order(tree); 36. printf("\n"); 37. order(tree); 38. avltree_deleteNode(tree, 9); 39. printf("\n"); 40. order(tree); 41. 42. }
8.并查集
看到这个名字就很容易理解，并查集是对一组集合做合并与查找操作的数据结构（集合是不相交的）。但是按照什么标准对数据合并（即分类）与查找取决于业务里需要进行什么样的分类。下面介绍一下并查集的抽象数据类型和其查找的一个核心思维。
node 每个节点的父节点 rank 树的高度
1. int node[100];//每个结点 2. int rank[100];//树的高度
虽然并查集在抽象理解上是一个树形的结构，可是实际应用的时候一般是用数组实现的，实际应用时会给每个元素一个数字，node数组用来存储该节点的父节点数字，如下图 node[1] = 4，根节点的指针要指向自己。
①初始化操作
这里的初始化非常简单，上面说过根节点的指针指向自己就行，再把每个根节点的高度rank赋值为0就可以了，代码如下。
1. void makeSet(int size) 2. { 3. for (int i = 0; i < size; i++) 4. { 5. node[i] = i; 6. rank[i] = 0; 7. } 8. }
②合并操作
合并操作必须要在查找操作之前解释，因为查找操作里的大部分操作是为了优化合并操作的复杂度而存在的，在刚开始每个元素都是一个独立的树，我们需要把这些元素按照自己想要的规则合并成各种集合，我们只要先判断需要合并的两个树那个树的高度大，就把那个小的树合并到大树里，将小树的根节点设置为大树，将大树的rank增加，具体代码如下（find是查找操作的函数，返回值是输入值所在树的根节点的值）
1. void Unite(int x, int y) 2. { 3. x = find(x); 4. y = find(y); 5. if (x == y) 6. { 7. return;//这两个元素本身就已经在一个集合里面了 8. } 9. //判断两棵树的高度 决定谁是谁的子树 （针对集合和集合之间的合并） 10. if (rank[x] < rank[y]) 11. { 12. node[x] = y; 13. rank[y] += rank[x]; 14. } 15. else 16. { 17. node[y] = x; 18. rank[x] += rank[y]; 19. } 20. }
但这样的代码其实还是有问题的，因为如果按照上面的方式合并，我们最终得到的是一个如下图的单链表，和上面展示的最终并查集的样子不一样，而将这种单链表形态转变为并查集的最后操作我们其实是在查找里完成的。
③查找操作
除了递归找到父节点之外，为了让单链表形态的集合改变，我们在递归的同时要返回递归找到的根节点，并让递归路径上所有的节点都直接指向该节点，画图比较难表达这种操作，大家就直接看代码吧。
1. int find(int x) 2. { 3. if (x == node[x]) 4. { 5. return x; 6. } 7. 8. return node[x] = find(node[x]);//在第一次查找时 将结点直接连接到根节点 9. 10. }
由于对于不同的需求并查集分类的方式是不同的，这里的并查集学习也只能给出合并和查找的操作，main函数即测试用例需要带到具体的环境里运用体会，这里就不演示了。
9.线索二叉树
线索二叉树是在普通二叉树上利用指针域为空（之后叫做空链域）的一些节点做改进，形成的遍历更加快捷的一种树。之前我们对二叉树进行的遍历操作主要都是用中序遍历去发现里面树的规律，线索二叉树用空链域记录了每个节点的前驱和后继，说着比较抽象，下面看图片。
上图是原来不做任何处理的二叉树，线索二叉树要先把上图变成下图这样。
这样我们做第二次遍历的时候，我们就可以通过一种单链表的方式去遍历完这个二叉树，这就是线索二叉树的原理。但这个时候会出现一个问题，之前我们遍历结束的点都是当遇到NULL时停止，现在我们如何判断结束的点呢，下面通过解释他的抽象数据类型来解决这个问题。
data 值域 leftright 左右指针域 left_type right_type 标志位（0表示孩子，1表示线索）
1. typedef struct ThreadTree { 2. int data; 3. struct ThreadTree* left, * right; 4. int lefy_type, right_type;//标志位 0代表孩子 1代表线索 5. }Node;
与普通二叉树的抽象数据类型相比可以发现这里多了两个标志位，这个的作用就是用来表示这时候的左右指针域究竟表示的是孩子还是线索，这样就可以解决我们上面说的问题，下面我们以0表示孩子，1表示线索书写代码。
①线索化
二叉树前面插入操作核心思想与与普通二叉树无差别，线索二叉树的线索化都是在第一次遍历之后形成的而不是插入时形成的，下面的代码以中序遍历为例来写一遍中序线索化。我们在这里引入一个pre变量来记录node节点上一次到达的位置。这时候我们就可以在遍历过的位置上用pre表示node的前驱，node表示pre的后继，如果之前排序二叉树的中序遍历理解的比较透彻的话那下面遍历实现的线索化应该是很容易看懂的。
1. Node* pre;//设定一个跟随的指针 2. //中序线索化 3. void inOrderThreadTree(Node* node) 4. { 5. //如果当前结点为NULL 直接返回 6. if (node == NULL) 7. { 8. return; 9. } 10. inOrderThreadTree(node->left); 11. //线索化过程 先处理前驱结点 12. //如果结点的左子树为NULL 13. if (node->left == NULL) 14. { 15. //设置前驱结点 16. node->lefy_type = 1; 17. node->left = pre; 18. } 19. //如果右子节点为NULL 处理前驱的右指针 20. if (pre!=NULL && pre->right == NULL) 21. { 22. pre->right_type = 1; 23. pre->right = node; 24. } 25. //每处理完一个节点 当前结点就是下一个结点的前驱 26. pre = node; 27. //处理右子树 28. inOrderThreadTree(node->right); 29. }
②链式遍历
在我们经过一次中序遍历之后线索化就已经完成了，这时候我们就可以对二叉树实现链式的遍历，这里的代码也不难，代码如下。
1. void inOrderTraverse(Node* node) 2. { 3. //得到根节点 4. if (node == NULL) 5. { 6. return; 7. } 8. //先找到最左边的结点 9. while (node!= NULL && node->lefy_type == 0) 10. { 11. node = node->left; 12. } 13. //向右不断遍历 14. while (node != NULL) 15. { 16. printf("%d", node->data); 17. node = node->right; 18. } 19. }
线索二叉树的应用场景不多，而且数据量不大的时候线索二叉树是表现不出他的优势的，现在已知的应用场景有路由器CIDR地址划分时就用到了线索化。
