分治法求解二叉树深度
若一个树没有孩子，则它的深度为1；
若一个树只有左孩子，则它的深度就是左孩子的深度+1；
若一个树只有右孩子，则它的深度就是右孩子的深度+1；
若一个树有两个孩子，则它的深度就是两个孩子中较深的那颗深度+1。
由此可以递归得到该树的高度。
分治法：棋盘覆盖问题
若棋盘规格是1*1，则不用填充；
若棋盘规格大于1*1，则将棋盘分割成四个子棋盘。判断特殊点在哪一个子棋盘中，进入该棋盘继续覆盖，而对其他子棋盘，设置边界点为新特殊点（填充这3个边界点即是填充了一个L型骨牌），并对各个子棋盘继续覆盖。
分治法：平面最近点对问题
当一个点集中只有两个点时，它们的距离就是最近距离；
当一个点集中有三个点时，它们的距离也可以直接求出；
当一个点集中的点数量大于3时，则将数组拆分成两半，分别计算左右子集的最近距离的平方d（将数量>3的数组一直拆分，最后到只有2个或3个点的点集时即能求解），收集距离中线两侧小于d的点，在这些点中寻找垂直距离小于d的两个点，若存在则说明其为当前能找到的最近点对，更新d为这两点的距离。
分治法求第K大元素
k大元素不就是第(n-k+1)小元素么 = =
-
#include<iostream>
-
#include<algorithm>
-
using namespace std;
-
-
/***************************************
-
* 选择第k小元素算法
-
*
-
* 输入：元素数组A[]，元素个数n，求的k
-
* 输出：第k小元素
-
***************************************/
-
template<class Type>
-
Type select(Type A[], int n, int k){
-
int i,j,s,t;
-
Type m,*p,*q,*r;
-
if(n<38){ // 如果元素个数小于38：则直接排序
-
sort(A,A+n);
-
return A[k-1];
-
}
-
p = new Type[3*n/4];
-
q = new Type[3*n/4];
-
r = new Type[3*n/4];
-
for( i=0; i<n/5; i++){ // 五个一组，把每组的中值元素存放进数组p
-
mid(A,i,p);
-
}
-
m = select(p, i, i/2+i%2); // 递归调用，取得中值元素存入m
-
i = j = s = 0;
-
for( t=0; t<n; i++){ // 按<m、=m、>m把数组分成三组
-
if(A[t]<m){
-
p[i++] = A[t];
-
}else{
-
if(A[t]==m){
-
q[j++] = A[t];
-
}else{
-
r[s++] = A[t];
-
}
-
-
}
-
}
-
if(i>k){ // 若k<i，则该元素就在数组p中，进入p继续查找
-
return select(p,i,k);
-
}else{
-
if(i+j>=k){ // 若i<k<i+j，则该元素在q数组中，即值为m
-
return m;
-
}else{ // 若k>i+j，则该元素在r数组中，进入r继续寻找
-
return select(r,s,k-i-j);
-
}
-
}
-
}
-
-
/***************************************
-
* 计算中值元素
-
*
-
* 输入：元素数组A[]，组号i
-
* 输出：存放中值元素的数组p[]
-
***************************************/
-
template<class Type>
-
void mid(Type A[], int i, Type p[]){
-
int k = 5*i;
-
if(A[k]>A[k+2]){
-
swap(A[k], A[k+2]);
-
}
-
if(A[k+1]>A[k+3]){
-
swap(A[k+1], A[k+3]);
-
}
-
if(A[k]>A[k+1]){
-
swap(A[k],A[k+1]);
-
}
-
if(A[k+2]>A[k+3]){
-
swap(A[k+2],A[k+3]);
-
}
-
if(A[k+1]>A[k+2]){
-
swap(A[k+1],A[k+2]);
-
}
-
if(A[k+4]>A[k+2]){
-
p[i] = A[k+2];
-
}else{
-
if(A[k+4]>A[k+1]){
-
p[i] = A[k+4];
-
}else{
-
p[i] = A[k+1];
-
}
-
}
-
}
-
-
int main(){
-
int n,m;
-
-
cout<<"请输入数组元素个数：";
-
cin>>n;
-
-
cout<<"请输入要求的k：";
-
cin>>m;
-
-
int *A = new int[n];
-
int i;
-
-
cout<<"请输入数组元素："<<endl;
-
for(i=0;i<n;i++){
-
cin>>A[i];
-
}
-
-
cout<<"第"<<m<<"大元素是：";
-
cout<<select(A,n,n-m+1)<<endl; // 输出第(n-m+1)小元素<=>第m大元素
-
-
return 0;
-
}
