正文
减治法
⚫ 减治技术：利用一个问题给定实例的解与同样问题较小实例的解之间的某种关系，可将原问题从顶至下，或从底至上地解决。从顶至下导致递归算法，从底至上导致增量法（注：从求解问题的一个较小实例开始，迭代实现，往往要好于递归）。
⚫减治法的三种变化形式：减去一个常量、减去一个常量因子、减去的规模可变。
减常量：每次迭代总是从实例中减去一个相同的常量（一般来说，这个常量为1)。
例如，计算a"的值，f(n)=a"
乘法为基本操作，上述减常量算法时间效率为O(n)。
减常因子：每次迭代总是从实例的规模中减去一个相同的常数因子(一般来说，这个常数因子为2)。
和上述同样的例子，计算a"的值，f(n)=a"
乘法为基本操作，上述减常因子算法效率为O(log n)。
减可变规模： 算法在每次迭代时，规模减小的模式可变。例如，欧几里得算法:
gcd(m,n) = gcd(n,m mod n)
插入排序
减治法最典型的案例之一便是插入排序。
插入排序思想:假设较小数组A[O..n-2]已排序好，为了得到一个大小为n的有序数组，在A[0..n-2]中找到一个合适位置，将A[n-1]插入该位置。迭代实现的插入排序伪代码如下:
InsertionSort(A[O..n-1]) //用插入排序对给定数组排序 //输入:n个可排序元素构成的一个数组A[0..n一1] //输出:非降序排列的数组A[0..n一1] for i <- 1 to n-1 do v <- A[i] j <- i-1 while j ≥ 0 and A[j] > v do A[j + 1] <- A[j] j <- j-1 A[j + 1] <- v
例子:对数组89,45,68,90,29,34,17排序：
插入排序
代码实现：
#include<stdio.h> #include<stdlib.h> void insort(int *a,int n) { printf("排序前为："); for(int i = 0; i < n;i++) printf("%d ",*(a + i)); } for(int i = 1; i < n;i++) { for(int j = i-1;j >= 0;j--) { if(*(a+j+1) < *(a+j)) //如果前面的数比后面大，就交换 { int t = *(a+j+1); *(a+j+1) = *(a+j); *(a+j) = t; } } printf("\n排序中："); //显示每循环一次之后的排序结果 for(int i = 0; i < n;i++) { printf("%d ",*(a + i)); } } printf("\n排序后为："); for(int i = 0; i < n;i++) { printf("%d ",*(a + i)); } printf("\n"); } int main(int argc,char * argv[]) { int *str = NULL; //存储要排序的数组 int n; //存储排序数组个数 printf("请输入要排序的个数："); scanf("%d",&n); str = (int *)malloc(n * sizeof(int)); //获取个数后，给str分配空间 printf("请输入要排序的数据（以空格隔开）："); for(int i = 0; i < n;i++) //循环将数据写入str中 { scanf("%d",(str + i)); } insort( str , n); //调用排序算法 }
二叉查找数
二叉树的节点包含排序项集合的元素，每个节点一个元素，对于每个节点，其所有左子树的元素都小于这个节点，其所有右子树的元素都大于这个节点。
二叉查找树查找一个键值v的过程:将v与树的根节点进行比较，若相等，直接返回，若小于，在左子树中继续查找，若大于，在右子树中继续查找。
算法的每次迭代，都简化为在一棵更小的二叉查找子树中查找（注:由于子树的高度是不一样的，因此，每次减少的规模可能是不一样的）。
在二叉查找树中查找与插入键具有相等的时间效率。最坏时间效率为0(n)（例如:当连续插入的键是一个递增或递减序列时），平均时间效率为0(log n)。
创建
算法思路：
二叉排序树的创建过程，实际上就是把一个结点加入到一颗二叉排序数中，并且保证其二叉排序性过程。
不断重复二叉排序树的插入操作。
二叉排序树的插入操作：
1.找插入位置
2.执行插入操作
/* create_sotr_tree:创建一颗二叉排序树 返回值： 二叉排序树的根节点指针 */ BiTNode *create_sort_tree() { //保存根结点的指针 BiTNode *r = NULL; //step1 从键盘上获取数据 int i = 0; char str[64] = {0}; //gets(str); /*for(int i = 0;i<64;i++) { scanf("%s",&str[i]); if(str[i] == '0') break; }*/ scanf("%s",str); while(str[i]) { //step2 创建新的数据结点 并且把数据写进去 BiTNode *pnew = malloc(sizeof(*pnew)); pnew->data = str[i]; pnew->lchild = NULL; pnew->rchild = NULL; r = inset_node(r,pnew); i++; } return r; }
插入与删除节点
插入与删除都有多种情况需要考虑
插入
二叉数是空数
遍历找到应该挂的位置，子树为空时挂上去
删除
删除的是叶子节点，直接删除
删除的节点有右子树
删除的节点有左子树
删除的节点有左右子树
//在一棵二叉排序树中增加结点 BiTNode *inset_node(BiTNode *r, BiTNode *pnew) { BiTNode *p = r;//遍历指针 用来查找挂结点的位置 if(r == NULL)//从无到有 这棵树是一颗空树 那么新插入的结点就是数本身 { return pnew; } if(pnew == NULL) { return r; } while(1) { if(pnew->data < p->data) { if(p->lchild == NULL)//如果p左孩子为空 直接挂上去 { p->lchild = pnew; break; } p = p->lchild; } else if(pnew->data > p->data) { if(p->rchild == NULL)//如果p右孩子为空 直接挂上去 { p->rchild = pnew; break; } p = p->rchild; } else { printf("data repeated\n"); break; } } return r; } BiTNode *delete_node(BiTNode *r,u4 x) { //step1 找到要删除的节点px，以及他的父节点pf BiTNode *px = r; BiTNode *pf = NULL; while(px) { if(px->data == x+48) { break; } else if(px->data > x) { pf = px; //确保pf指向px 的父节点 px = px->lchild; } else //px->data < x { pf = px; px = px->rchild; } } if(px == NULL) { return r; } //分情况删除 if(px == r && px->lchild == NULL && px->rchild == NULL) //根节点且左右节点都为空 { free(r); printf("删除节点后，树为空！\n"); return NULL; } else if(px == r && px->lchild == NULL) //根节点且左节点为空 { r = r->rchild; free(px); } else if(px == r && px->rchild == NULL) //根节点且右节点为空 { r = r->lchild; free(px); } else if(px->lchild == NULL && px->rchild == NULL) //为叶子节点 { if(pf->lchild == px) { pf->lchild = NULL; free(px); } else { pf->rchild = NULL; free(px); } } else if(px->lchild != NULL && px->rchild == NULL) //只有右孩子 { if(pf->lchild == px) { pf->lchild = px->lchild; px->lchild = NULL; free(px); } else { pf->rchild = px->lchild; px->lchild = NULL; free(px); } } else if(px->lchild == NULL && px->rchild != NULL) //只有左孩子 { if(pf->lchild == px) { pf->lchild = px->rchild; px->rchild = NULL; free(px); } else { pf->rchild = px->rchild; px->rchild = NULL; free(px); } } else //px->lchild != NULL && px->rchild != NULL //有两个度的节点 { BiTNode *p = px; BiTNode *pre = NULL; p = p->rchild; while(p->lchild) { pre = p; p = p->lchild; } px->data = p->data; pre->lchild = NULL; free(p); } return r; }
查找
/*在一棵二叉排序树中查找节点值 参数: @BiTNode *r：传入的二叉排序数 @int n：要查找的数 返回值： char *：返回这个值在树中的顺序（如“01101”，左0右1） */ char *Find_node(BiTNode *r, int n) { BiTNode *p = r; //遍历指针 用来查找结点的位置 char *str = NULL; //用来记录查找时的顺序 str = (char *)malloc(sizeof(char)*128); if(r == NULL) //这棵树是一颗空树,直接返回 { return str; } for(int i = 0; ;i++) { if(n < p->data) //n小于当前节点值，往左走，str中记0 { sscanf("0",(str+i)); if(p->lchild == NULL)//如果p左孩子为空 直接挂上去 { printf("二叉排序树中没有这个树\n"); str = NULL; break; } p = p->lchild; } else if(n > p->data) //n小于当前节点值，往右走，str中记1 { sscanf("1",(str+i)); if(p->rchild == NULL)//如果p右孩子为空 直接挂上去 { printf("二叉排序树中没有这个树\n"); str = NULL; break; } p = p->rchild; } else { break; } } return str; }
