7.双端队列
在说双端队列的操作之前先认识一下什么是双端队列。从功能上来描述，双端队列像是栈和队列的集合，他同时有着这两个数据结构的功能， 一般用于各种需要灵活使用栈或队列的底层，比如c++stl的栈这些。双向队列在实际应用中只有两种，一种是数据只能从一段加入而可以从两端取数据，另一种是可以从两端加入但从一段取数据，从而同时实现栈和队列的功能。我这次举得事例是一端插入，两端删除的以顺序表实现的双端队列（方式上能实现两端增和删但是实际中不这么用）
他的抽象数据类型如下：
double_shun_queue 数组用来存放数据 left 左指针 right 右指针
maxsize 目前最大存储数量 size 当前元素个数
1. int* double_shun_queue;//数组用来表示队列 2. int left;//左指针 3. int right;//右指针 4. int maxsize=5;//目前队列最大存储数量 5. int size;//当前元素个数
①插入操作
由上面对双端队列的操作可知，插入操作一共分为左插和右插两个。因为我这次举得例子是一端插入的，所以代码会和两端插入的不同，不过原理都是一样的。
这里的插入与栈里的一样，比如进行一个右插，我们就把数据插在right所在的位置，并把right++,有一个需要注意的点是当我们执行右插操作的时候，因为是要从右边插入，所以我们初始化的时候要把两个指针的初始位置放在顺序表的最左边，同理，如果我们要执行左插我们就要在初始化的时候把两个指针都放在顺序表的最右边（以上都是针对一端插入两端输出的操作。两端插入一段输出的原理相似自己思考一下就行）还有一个要注意的地方是，因为后面要进行删除的操作，所以会出现和之前的队列一样的问题，所以这里的双端队列必须是环形的，并且判满和判空的操作也不一样。代码如下。
1. void insert_left_double_shun_queue(int key)//左插操作 2. { 3. if (isfull()) 4. { 5. printf("队列满了"); 6. system("pause"); 7. } 8. else 9. { 10. if (isempty()) 11. { 12. left = right = maxsize; 13. double_shun_queue[--left] = key; 14. } 15. else 16. { 17. if (left == 0) 18. { 19. left = maxsize; 20. } 21. double_shun_queue[--left] = key; 22. } 23. size++; 24. } 25. } 26. 27. void insert_right_double_shun_queue(int key)//右插操作 28. { 29. if (isfull()) 30. { 31. printf("队列满了"); 32. system("pause"); 33. } 34. else 35. { 36. if (isempty()) 37. { 38. left = right = 0; 39. double_shun_queue[right++] = key; 40. } 41. else 42. { 43. if (right == maxsize) 44. { 45. right = 0; 46. } 47. double_shun_queue[right++] = key; 48. } 49. size++; 50. } 51. }
②删除操作
这里我们举的例子是一端输入两端输出（也就是两端删除），所以两端的删除操作也是都要实现的。之前不论是左插还是右插，不变的一点就是我们的左指针永远是我需要数据的起始位，右指针永远是我们需要数据的结束位。所以不管之前我们进行的是什么操作，我们的左删都是直接将left++（并还要考虑循环操作防止假溢出）。右删也同理。这里与栈队列相似的地方就是我们的删除操作既不删除内存也不删除数据，仅仅是移动了我们需要内容的指针而已。代码如下。
1. void delete_left_double_shun_queue()//左删 2. { 3. if (isempty()) 4. { 5. printf("队列空了"); 6. system("pause"); 7. } 8. else 9. { 10. if (left == maxsize - 1) 11. { 12. left = 0; 13. size--; 14. } 15. else 16. { 17. left++; 18. size--; 19. } 20. } 21. } 22. 23. void delete_right_double_shun_queue()//右删 24. { 25. if (isempty()) 26. { 27. printf("队列空了"); 28. system("pause"); 29. } 30. else 31. { 32. if (right == 0) 33. { 34. right = maxsize - 1; 35. size--; 36. } 37. else 38. { 39. right--; 40. size--; 41. } 42. }
③其他操作即main函数
接下来我们只要进行一个初始化操作，并把之前写的插入删除组合在一起，我们就能实现双端队列。如此事例左插左删是栈，左插右删是队列（右插左删是队列，右插右删是栈）。代码如下
1. #include <stdio.h> 2. #include <stdlib.h> 3. 4. void init_double_shun_queue() 5. { 6. double_shun_queue = (int*)malloc(maxsize * sizeof(int)); 7. size = 0; 8. } 9. 10. int isfull() 11. { 12. if (size == maxsize) 13. { 14. return 1; 15. } 16. else 17. { 18. return 0; 19. } 20. } 21. 22. int isempty() 23. { 24. if (size == 0) 25. { 26. return 1; 27. } 28. else 29. { 30. return 0; 31. } 32. } 33. 34. int main() 35. { 36. init_double_shun_queue(); 37. insert_right_double_shun_queue(1); 38. insert_right_double_shun_queue(2); 39. insert_right_double_shun_queue(3); 40. delete_left_double_shun_queue(); 41. insert_right_double_shun_queue(4); 42. delete_left_double_shun_queue(); 43. insert_right_double_shun_queue(5); 44. insert_right_double_shun_queue(6); 45. insert_right_double_shun_queue(7); 46. for (int i = 0; i < 5; i++) 47. { 48. printf("%d\n", double_shun_queue[i]); 49. } 50. system("pause"); 51. return 0; 52. }
三、树
树形结构和线性结构最大的区别就是：线性结构是一对一的关系，而树是一对多的关系。
每个树的第一个节点是根节点，最下面一行的节点是叶子结点。上面的节点是下面节点的父节点，下面节点是上面节点的子节点。节点的度就是该节点子节点的个数。树的度是这颗树里拥有子节点数量最多的父节点所拥有的子节点数。树的深度就是现在这个树有几层（比如上面树的深度是3）
1.树的基本存储结构
接下来认识一下树的基本存储结构，一共有三个：双亲表示法，孩子表示法，孩子兄弟表示法。
①双亲表示法
这里的每个节点通过存储他的父节点去寻找他的上一个节点。任何一种算法脱离不开两种书写的方式，一种是顺序存储，一种是链式存储。那么上面这个用顺序存储怎么实现呢？非常简单，具体看下图。
这里由于各种初始化，插入，删除的操作都和链表顺序表等之前讲过的一样，这里就不细说了直接放代码。
1. #include <stdio.h> 2. #include <stdlib.h> 3. 4. /* 5. 双亲表示法 6. */ 7. 8. typedef struct treenode//(若要字符记得修改parr Int) 9. { 10. int date; 11. int parent;//该节点父节点的下标 12. }node; 13. 14. node* nod[5]; 15. int size;//当前元素个数 16. int maxsize;//当前最大元素个数 17. 18. void init_parent_tree();//初始化 19. void add_root(int key);//创建父节点并插入数据，根节点的父节点下标默认为-1 20. void insert_kid(int key,int parent); 21. int find_parent(int parent); 22. 23. void init_parent_tree() 24. { 25. maxsize=5; 26. size=0; 27. } 28. 29. void add_root(int key) 30. { 31. node*new_node=(node*)malloc(sizeof(node)); 32. new_node->date=key; 33. new_node->parent=-1; 34. nod[size]=new_node; 35. size++; 36. } 37. 38. void insert_kid(int key,int parent) 39. { 40. if(size==maxsize) 41. { 42. printf("树满了"); 43. system("pause"); 44. } 45. else 46. { 47. int parent_index=find_parent(parent); 48. if(parent_index==-1) 49. { 50. printf("父节点不存在"); 51. system("pause"); 52. } 53. else 54. { 55. node*new_node=(node*)malloc(sizeof(node)); 56. new_node->date=key; 57. new_node->parent=parent_index; 58. nod[size]=new_node; 59. size++; 60. } 61. } 62. } 63. 64. int find_parent(int parent) 65. { 66. for(int i=0;i<size;i++) 67. { 68. if(parent==nod[i]->date) 69. { 70. return i; 71. } 72. } 73. return -1; 74. } 75. 76. int main() 77. { 78. init_parent_tree(); 79. add_root(1); 80. insert_kid(2,1); 81. system("pause"); 82. return 0; 83. }
这一种表示方法能很好的找到父亲节点，但是他是没有办法找到孩子节点和兄弟节点的（同一父节点的几个节点互为兄弟节点）。但这时候就一定要用到我们下面的孩子兄弟表示法吗？其实只要再给我的每个节点加一块内存使他指向自己最近的一个兄弟就好了。
下面的各种表示方法也就是这么演化过来的，只是看你需要的侧重点是哪一个你就加上哪一部分的功能，具体的表示方法并没有这么死板。
②孩子表示法
从图来看孩子表示法和双亲表示法只是一个箭头方向的差别，但是这就会造成一个问题，一个节点要同时指向多个节点。这样我们每个节点就不知道要放多少固定内存去存放指向下一个节点的内存了，那这里就用到了链表的特性，于是孩子表示法的存储方式是在双亲表示法的顺序表上加了链表，具体如下。
实现代码如下
1. #include <stdlib.h> 2. #include <stdio.h> 3. 4. /* 5. 孩子表示法 6. */ 7. 8. typedef struct linklist 9. { 10. int data;//存放下标 11. struct linklist* next; 12. }linknode; 13. 14. typedef struct child 15. { 16. int data; 17. struct linklist* next; 18. }child; 19. 20. child* node_array[20]; 21. int size; 22. int maxsize; 23. 24. void init(int key); 25. int find_parent(int parent, int key); 26. void great_tree(int parent, int key);//创造新节点 27. 28. void init(int key) 29. { 30. size = 1; 31. maxsize = 20; 32. node_array[0] = (child*)malloc(sizeof(child)); 33. node_array[0]->data = key; 34. node_array[0]->next = NULL; 35. } 36. 37. int find_parent(int parent, int key) 38. { 39. for (int i = 0; i < size; i++) 40. { 41. if (node_array[i]->data == parent) 42. { 43. return i; 44. } 45. } 46. return -1; 47. } 48. 49. void great_tree(int parent, int key)//创造新节点 50. { 51. int index = find_parent(parent,key); 52. if (index == -1)//不存在这个父节点 53. { 54. 55. } 56. else 57. {//这里懒得判断是否满了 58. node_array[size] = (child*)malloc(sizeof(child));//在顺序表里存放这个节点的值 59. node_array[size]->data = key; 60. node_array[size]->next = NULL; 61. 62. 63. linknode* new_node = (linknode*)malloc(sizeof(linknode));//在父节点的链表里存放该节点的下标 64. new_node->data = size; 65. new_node->next = node_array[index]->next; 66. node_array[index]->next = new_node; 67. size++; 68. } 69. } 70. 71. int main() 72. { 73. init(1); 74. great_tree(1, 2); 75. great_tree(1, 3); 76. great_tree(2, 4); 77. great_tree(2, 5); 78. linknode* temp = node_array[1]->next; 79. while (1) 80. { 81. printf("%d ", node_array[temp->data]->data); 82. temp = temp->next; 83. if (temp == NULL) break; 84. } 85. system("pause"); 86. return 0; 87. }
ABCDE是我在该节点存放的数据，而后面箭头指向的是该节点的子节点的下标，这就是孩子表示法。
③孩子兄弟表示法
其实孩子兄弟表示法就是在孩子表示法加上一个兄弟节点，原理上都是一样的。
代码如下
1. #include <stdlib.h> 2. #include <stdio.h> 3. 4. /* 5. 孩子兄弟表示法 6. */ 7. typedef struct childbro 8. { 9. int key;//数据 10. struct childbro* child;//孩子指针 11. struct childbro* sibling;//兄弟指针 12. }childbro; 13. 14. childbro* root = NULL; 15. 16. void init(int key) 17. { 18. root = (childbro*)malloc(sizeof(childbro)); 19. root->key = key; 20. root->child = NULL; 21. root->sibling = NULL; 22. } 23. 24. childbro* find_node(childbro* node, int key) 25. { 26. static childbro* temp = NULL; 27. if (node->key == key) 28. { 29. temp = node; 30. } 31. 32. if (node->sibling != NULL) 33. { 34. find_node(node->sibling, key);//这里只改变temp所以不用接受返回值 35. } 36. 37. if (node->child != NULL) 38. { 39. find_node(node->child, key); 40. } 41. 42. return temp; 43. } 44. 45. void insert(int key, int parent)//插入数据 46. { 47. childbro* temp = find_node(root, parent);//定位节点 递归 48. if (temp == NULL) 49. { 50. printf("没有这个节点"); 51. system("pause"); 52. } 53. else 54. { 55. if (temp->child == NULL)//判断要插入的父节点有没有孩子，有则插在孩子的兄弟节点上 56. { 57. childbro* node = (childbro*)malloc(sizeof(childbro)); 58. node->key = key; 59. node->child = NULL; 60. node->sibling = NULL; 61. temp->child = node; 62. } 63. else 64. { 65. temp = temp->child; 66. childbro* node = (childbro*)malloc(sizeof(childbro)); 67. node->key = key; 68. node->child = NULL; 69. node->sibling = temp->child; 70. temp->sibling = node; 71. } 72. } 73. } 74. 75. int main() 76. { 77. init(1); 78. insert(2, 1); 79. insert(3, 1); 80. childbro* temp = root; 81. printf("%d %d", (temp->child)->key, ((temp->child)->sibling)->key); 82. return 0; 83. }
2.递归
递归一般的由一个递归函数体和递归函数出口组成。
这里就以最简单的一个累加来举例子
这里就实现了一个5一直加到1的累加，具体的实现过程是下面这样的。
如果一个递归写的不好，是有可能会有效率低和占内存的问题的，但一个好的递归能让代码可读性非常的高并且容易书写，在写项目时可以大胆的使用。
为了优化递归占用内存大的问题，出现了尾递归来优化递归操作，之前递归占用内存大的主要原因就是我运行一个函数进入下一个函数时，在运行的函数其实并没有结束，只是挂起作为等待的状态，但是尾递归，进入下一个函数时此函数将结束，于是不会有挂起的函数占用内存。
1. int add(int x,int sum)//尾递归 2. { 3. if(x == 1) return sum; 4. else add(x - 1,sum + x); 5. }
不是所有的递归都能用尾递归优化，也不是所有的编译器都能对尾递归做优化，大部分老的编译器是不能优化尾递归的。
3.树，二叉树，森林之间的转换
这一部分的内容主要运用于考试
①普通树转成二叉树：
比如我们要将下面的树转化为二叉树
我们先要连接所有的兄弟节点，如下
第二步，去掉除了节点与第一个孩子的连线和兄弟之间的连线，处理完就会变成二叉树。
②森林转化成二叉树：
第一步，先把每一颗小树转化成二叉树
第二步，第一棵二叉树不动，每后一个二叉树作为前一个二叉树根节点的右子节点。
③二叉树转化成树、森林：
第一步，如果节点x是其双亲节点y的左孩子，就把x的右孩子，右孩子的右孩子和节点y连起来
第二步，去掉右孩子之间的连线
4.二叉树基础知识
先讲一些基本概念。度小于等于2的树是二叉树。只有左子树或只有右子树的叫斜树。满二叉树： 只存在度为0的节点和度为2的节点。完全二叉树：所有节点必须按照从上到下，从左到右来排，也就是说如果有节点的上层存在空的位置，或者有节点的左边存在空的位置，那这个树就都不是完全二叉树。扩展二叉树：把一个普通的树补成满二叉树（补null等不可能存在的符号即可）。
还有就是一些考试要用的计算性质，这里就直接放这里。（下面所有第一个节点的下标假设是从1开始的）
①二叉树第i层最多有 2 ^ (i - 1)个节点
②深度为k的二叉树最多有2 ^ k - 1个节点
③这里我们设度为0的节点为n0，度为1的节点为n1，度为2的节点为n2，因为节点数等于节点之间连接线的数量+1，所以n2 + n1 + n0 = 2 * n2 +n1 + 1,所以最终得出最后一个结果 n0 = n2 + 1
④具有n个节点完全二叉树的深度为（log2n） + 1向下取整
⑤一个树有n个节点，且为完全二叉树，那根据性质④我们就知道他的深度是log2n+1向下取整，我们将所有的节点按层次编号为i（编号大小自上而下递增，自左向右递增），对于任意一个节点，如果i = 1则为该树的根节点，如果i > 1，那么他的双亲节点的编号一定为i / 2。如果2i > n，那么节点i没有左孩子（当然也就没有右孩子），如果2i + 1 > n，那么节点i一定没有右孩子
到现在不论是什么数据结构说到底其实都是由链式存储和顺序存储来实现的，链式存储表示二叉树的方法比较容易想到，也是我们平常用的最多的，这里稍微再介绍一下顺序存储。怎么实现顺序存储二叉树呢？用一个二维数组，如下。
这里我们既然用顺序存储，我们可以把所有的二叉树都补成一个一直到最后一层都有数据的二叉树，像下图这样。
为什么要这么操作呢，从前面的学习我们可以知道顺序存储最大的优势就是查找迅速 ，所以我们可以通过快速的知道子节点的下标去实现二叉树快速的查找，上面那种二维数组的方法便可以改成如下图存储的方法。
那这个怎么能找到子节点的下标呢？我们之前对二叉树进行了一个处理，将原来的二叉树补成了一个满二叉树，把原先没有的地方制NULL就可以，这时候根据我们之前学到的性质，当我们存储的第一个下标从0开始的时候（之前是从1开始），假设节点为i,那他的子节点下标就分别为2i+1 和2i+2。这种方法能快的实现查找操作，但缺点是比较的浪费空间，接下来主要介绍链式的存储。
5.二叉树的遍历
这里介绍二叉树的三种遍历方式 ：前序遍历，中序遍历，后序遍历。这是用来遍历二叉树的方式，就像我们通过i++遍历数组一样，三种不同的遍历方式在不同的时候会起到不同的作用，这里我们只需记住操作，具体有什么作用后面用到了就知道了。
前序遍历:先访问根结点,然后前序遍历左子树,再前序遍历右子树。
中序遍历:根结点开始,中序遍历根结点的左子树,然后访问根结点和右节点。
后序遍历:从左到右先叶子后结点的方式遍历访问左右子树,最后访问根结点。
上面三句看了其实不能很好的帮助我们理解这三种遍历，主要结合代码，一下就能看出前中后遍历的区别和实现，所以上面那三句看不懂可以放过。
①前序遍历
1. void In_Order(BTnode *root) 2. { 3. if (root == NULL) 4. { 5. printf("NULL "); 6. return; 7. } 8. printf("%d ", root->data); 9. In_Order(root->left); 10. In_Order(root->right); 11. }
1. void In_Order(BTnode *root) 2. { 3. if (root == NULL) 4. { 5. printf("NULL "); 6. return; 7. } 8. In_Order(root->left); 9. printf("%d ", root->data); 10. In_Order(root->right); 11. }
③后序遍历
1. void In_Order(BTnode *root) 2. { 3. if (root == NULL) 4. { 5. printf("NULL "); 6. return; 7. } 8. In_Order(root->left); 9. In_Order(root->right); 10. printf("%d ", root->data); 11. }
从上面的三种遍历就很容易看出，printf在两个遍历语句的（前中后）位置就说明该函数是（前中后）遍历。
④层序遍历
这个遍历实现二叉树一层一层向下遍历（从上到下，从左到右）的操作，想要实现这种操作只靠递归是不行的，还需要用到之前队列的知识
一开始我们先存一个根节点进去，比如我们现在的树如下
现在我们的队列里只有1，然后我们就做出队操作，并且我们以后每次的出队操作，我们都会把该出队节点的两个子节点入队，重复以上操作我们就能够实现层序遍历。最后看是否遍历完毕是通过判断队列是否为空完成的。（这一块的代码就不放了，原理差不多，偷个小懒）
6.二叉排序树
性质：只要左子树不空，则左子树所有节点的值小于根节点，右子树如果不空，右子树所有节点必须大于根节点。
二叉排序树被创造的初衷是方便于我们的查找，下面是他的抽象数据类型
1. typedef int BTDatatype; 2. typedef struct BinaryTreeNode 3. { 4. BTDatatype data; 5. BTDatatype size; //身份证，如果有相等的值，size+1 6. struct BinaryTreeNode *left; 7. struct BinaryTreeNode *right; 8. } BTnode;
①插入操作
下面我们模拟二叉排序树是如何形成的，这里我们假设有一组数据如下，我们要把他放到二叉排序树后里面
先把第一个数据放在根节点，然后看第二个数据3，比8小，放在8的左节点，10比8大放在8右节点，1比8小放在8左节点，8左节点已经有数据3,1比3小，于是1放在3的左节点，以此类推。
最后得到的二叉树是长这样的，但是这样的二叉树有什么用呢？这样的树看起来确实非常混乱，但是用中序遍历遍历这个树之后，得到的数据是1 3 4 6 7 8 10 13 14 是有序的
1. void Push(BTnode **proot, BTDatatype x) //插入 2. { 3. BTnode *prev = NULL; //指向前一个节点 4. BTnode *temp = *proot; 5. 6. while (temp != NULL) //寻找要插入的位置 7. { 8. prev = temp; 9. if (x < (temp)->data) //如果插入的数据小于root，就往左边插入 10. { 11. temp = (temp)->left; 12. } 13. else if (x > (temp)->data) //如果插入的数据大于root，就往右边插入 14. { 15. temp = (temp)->right; 16. } 17. } 18. 19. if (prev == NULL) 20. { 21. BTnode *newnode = (BTnode *)malloc(sizeof(BTnode)); 22. newnode->data = x; 23. newnode->left = NULL; 24. newnode->right = NULL; 25. 26. *proot = newnode; 27. } 28. else if (x < prev->data) 29. { 30. BTnode *newnode = (BTnode *)malloc(sizeof(BTnode)); 31. newnode->data = x; 32. newnode->left = NULL; 33. newnode->right = NULL; 34. 35. prev->left = newnode; 36. } 37. else if (x > prev->data) 38. { 39. BTnode *newnode = (BTnode *)malloc(sizeof(BTnode)); 40. newnode->data = x; 41. newnode->left = NULL; 42. newnode->right = NULL; 43. 44. prev->right = newnode; 45. } 46. }
②删除操作
对于二叉排序树的删除，我们一般分为三种情况
第一种情况：删除的节点是叶子节点，那么这时候直接删除就好，因为他删除之后对整个树不会造成任何其他的影响。
第二种情况：删除的节点只有一个孩子，这时候我们只要把他的孩子移动到被删除的位置就行了
第三种情况：删除的节点有两个孩子，从二叉排序树实现的功能上来说我们最终要实现的是在最后有序数列里把那个数据给删掉，所以我们其实需要的是一个能够代替原来那个节点的数据，该数据需要满足左边的数全都小于他，右边的数都大于他，那这个树怎么找呢，这里直接放结论：先进入到被删除的节点的左节点，这时候一直进入右节点直到右节点为NULL为止。现在所停留的节点就是那个可以替换原来删掉内容的节点，然后我们你把这个节点替换上去，而这个替换上去节点原来的位置我们就当做情况一、二来删除就行了。
像这里7就是替换被删除的8的数据。
1. void Del(BTnode *node) //node是要删除的节点 2. { 3. BTnode *tmp = NULL; 4. 5. //删除只有一个孩子的节点,间接的吧叶子节点删除 6. if (node->left == NULL) 7. { 8. tmp = node; 9. node = node->right;//这句话其实应该是改变他前一个节点的子节点，这里写错了，下面同，大家理解意思就行 10. } 11. else if (node->right == NULL) 12. { 13. tmp = node; 14. node = node->right; 15. } 16. 17. else //左右子树都不为空 18. { 19. tmp = node; 20. BTnode *s = node; 21. //找左子树的最大值 22. s = s->left; 23. while (s->right != NULL) 24. { 25. tmp = s; // tmp是s的上一个节点,解决删完后还有子树的情况 26. s = s->right; 27. } 28. 29. //先替换 30. node->data = s->data; 31. if (tmp != node) 32. { 33. tmp->right = s->left; 34. } 35. else 36. { 37. tmp->left = s->left; 38. } 39. } 40. }
