本人考研的算法笔记，包含考研数据结构会涉及到的算法，全部掌握让你考研算法题稳稳拿下！！
一、排序 1.插入排序算法思想：第i次插入排序：向i-1个有序数列中插入一个元素，使之称为含有i个元素的有序子序列。将当前元素和前驱元素比较，若大于则表示有序，不用改变；否则将该元素插入到前面，并且前面比它大的元素后移。
void InsertSort ( int a[] , int n ){int temp , i , j;for( i = 1 ; i=1 ; d = d/2)//步长变化for( i = d + 1 ; irchild)Q[rear++] = p->rchild;if (front == tag)//当遍历完当前行最后一个后{depth++;//层数增加并更新标记最后结点的tagtag = rear;}}return depth;}②递归
int Tree_Depth(BiTree T){if (T == NULL)return 0;int ldepth = Tree_Depth(T->lchild);int rdepth = Tree_Depth(T->rchild);if (ldepth > rdepth)return ldepth+1;elsereturn rdepth+1;} 6.求结点所在层数①非递归（简化）
用5①的非递归，当发现所查结点时输出depth+1（因为这时当前行还没运行完，depth还没有+1）
while (front lchild)Q[rear++] = p->lchild;if (p->rchild)Q[rear++] = p->rchild;if (front == tag)//当遍历完当前行最后一个后{depth++;//层数增加并更新标记最后结点的tagtag = rear;}}②递归
思想：若当前结点为空则返回0；若找到该结点则返回该结点的层数；遍历左右子树，若左右子树大于0则表示找到了，返回左/右子树的返回值
int Level(BTree T, BTNode* p, int depth){if(!T) return 0;if(T==p) return depth;int L = Level(T->lchild, p, depth+1);if(L>0) return L;//即找到了int R = Level(T->lchild, p, depth+1);if(R>0) return R;//即找到了return -1;//未找到} 7.求树的宽度①非递归int Width_Depth(BiTree T)（简化）
算法思想：利用5①的非递归遍历，在遍历每一行的时候都计算下一行的个数count=front-rear
int count=1, width=1;//count表示下一行的结点个数，max表示树的宽度(最大count)while (front lchild)Q[rear++] = p->lchild;if (p->rchild)Q[rear++] = p->rchild;if (front == tag)//当遍历完当前行最后一个后{tag = rear;width= rear - front;//计算当前行的个数if (width> max)max = width;//更新最大width}}return width;//返回width②递归
算法思想：开辟一个数组count[二叉树高度],遍历每一个节点,然后根据当前节点所在层次i,则执行count[i]++;最后遍历完求出最大的count即为二叉树宽度
int count[10];int Max = -1;void FindWidth(BiTree T, int k){if (!T)return;count[k]++;//k层结点数+1if (Max lchild, k + 1);//遍历左右子树FindWidth(T->rchild, k + 1);} 8.交换二叉树所有结点的左右子树①算法思想：使用层序遍历，但是在每次将左右子树入队时改为右左的顺序入队
②递归：算法思想：先序遍历（中序也可）左右子树，并且每次遍历将左右子树互换
void swap(BiTree T){BiTree q;//左右子树互换q = T->lchild;T->lchild = T->rchild;T->rchild = q;swap(T->lchild);//递归交换左右孩子的左右子树swap(T->rchild);} 9.求叶子结点个数-递归算法思想：1.若结点为空则返回0；2.若结点为叶子结点则返回1；3.否则返回左子树和右子树叶子结点的和。递归调用
int Degree0(BiTree T){if (!T)return 0;if (T->lchild == NULL && T->rchild == NULL)return 1;//若为叶子结点，返回1else return Degree0(T->lchild) + Degree0(T->rchild);//否则返回左右子树叶子数相加} 10.求度为2的结点个数-递归算法思想：1.若结点为空则返回0；2.若结点度为2则返回1+左右子树度为2的结点之和；3.否则返回左子树和右子树叶子结点的和。递归调用
int Degree2(BiTree T){if (!T)return 0;if (T->lchild != NULL && T->rchild != NULL)//若度为2，则return 1+ Degree2(T->lchild) + Degree2(T->rchild);//返回左右子树的度为2的结点个数和+1else return Degree2(T->lchild) + Degree2(T->rchild);//否则当前结点不是度为2，结点数不+1} 11.求度为1的结点个数-递归算法思想：1.若结点为空则返回0；2.若结点度为2则返回1+左右子树度为2的结点之和；3.否则返回左子树和右子树叶子结点的和。递归调用
int Degree1(BiTree T){if (!T)return 0;if (T->lchild != NULL && T->rchild == NULL)return 1+ Degree1(T->lchild) + Degree1(T->rchild);else if (T->lchild == NULL && T->rchild != NULL)return 1+ Degree1(T->lchild) + Degree1(T->rchild);else return Degree1(T->lchild) + Degree1(T->rchild);} 12.找最近公共祖先（求祖先都用后序遍历，因为栈保存的都是其祖先）算法思想：后序遍历当找到任意一个时保存当前栈中的元素，若两个都找到后退出循环并遍历找公共组先
BTNode* PrintParents_qp(BiTree T, BTNode *x,BTNode *y){if (!T) return NULL;BTNode *stack[10], *a[10], *b[10], *p = T, *r = NULL;//初始化栈int top = -1, pa = 0, pb = 0;while (top != -1 || p != NULL)//栈非空或树未遍历完{if (p)//走到最左边{if (p == x)//若找到x，则保存此时的栈{for (int i = 0; i rchild&&p->rchild != r)//若右子树并且未遍历{stack[++top] = p;//再把结点入栈并退出循环p = p->rchild;//右子树入栈}else//否则直接继续循环{r = p;p = NULL;}}}//找公共祖先int i=0;for(i=0; a[i] == b[i]&&irchild = NULL;return 1;//返回1，插入成功}else if (T->data == key)//若树中存在相同关键字，则插入失败return 0;else if (T->data > key)//插入到T的左子树中return BST_Insert(T->lchild, key);else//插入到T的右子树中return BST_Insert(T->rchild, key);} 14.2二叉排序树搜索操作算法思想：若等于结点的值或结点为空则返回结点；若小于结点的值则搜索左子树；若大于结点的值则搜索右子树
BTNode * BST_Search(BiTree T, int key)//非递归查找算法{while (T&&T->data != key)//若树非空或不等于结点值{if (key data)T = T->lchild;//若小于则向左查找elseT = T->rchild;//若大于则向右查找}return T;} 14.3二叉排序树构造操作算法思想：通过二叉树的插入算法，将数组中的所有结点都依次插入到二叉排序树中
void Creat_BST(BiTree &T, int str[], int n)//构造二叉树{T = NULL;//初始时T为空树int i = 0;while (i lchild&&T->lchild->data > T->data)return false;if (T->rchild&&T->rchild->data data)return false;return Decide(T->lchild) && Decide(T->lchild);} 15.判断是否是平衡二叉树算法思想:设置二叉树的平衡标记balance，标记返回二叉树T是否为平衡二叉树，若为平衡二叉树则返回1，否则返回0；h为二叉树T的高度。采用后序遍历的递归算法：
①若T为空，则高度为0，balance=1；
②若T为仅有根结点（即叶子结点），则高度为1，balance=1；
③否则，对T的左右子树进行递归操作，返回左右子树的高度和平衡标记，
T的高度为最高的子树的高度+1.
若左右子树的高度差大于1，则balance=0；
若左右子树的高度差小于等于1，*且左右子树都平衡时*，balance=1，否则balance=0.
void Judge_AVL(BiTree T, int &balance, int &h)//加上取地址符//balance返回是否是平衡二叉树，若是则返回1，否则返回0；h是二叉树的高度{int bl = 0, br = 0, hl = 0, hr = 0;//左右子树的平衡标记和高度if (!T) //空树，高度为0{h = 0;balance = 1;}else if (T->lchild == NULL && T->rchild == NULL){//若为根结点，则高度为1h = 1;balance = 1;}else{Judge_AVL(T->lchild, bl, hl);//判断左子树Judge_AVL(T->rchild, br, hr);//判断右子树h = (hl > hr ? hl : hr) + 1;balance = bl&&br;//若左右子树都平衡时，二叉树平衡elsebalance = 0;}} 五、串 1.存储结构①定长顺序存储
typedef struct SString selected选定{char ch[Max_Size];//每个分量存储一个字符int length;//串的实际长度}SString;②堆分配存储
typedef struct HString heap堆{char * ch;//按串长分配存储区，ch指向串的基地址int length;//串的实际长度}HString;③块链存储(eg大小为1的链表)
typedef struct LString{char data;//按串长分配存储区，ch指向串的基地址struct LString *Next;//指向下一个结点}LString; 2.KMP void get_next(String T, int next[]){int i = 1, j = 0;//i表示next的位置next[1] = 0;//初始化第一个值while (i