完全二叉探索ツリー(Complete Binary Search Tree)の実装
4842 ワード
タイトル:要素の個数、各要素の値を入力し、完全な二叉検索ツリーを実現します.入力:5 1 2 3 4 5出力:4 2 5 1 3コアアルゴリズム:このアルゴリズムは配列を容器として、すべての要素をA配列に入れた後、まずA配列の中のすべての要素を並べ替えて、それから木を左右の2つの部分に分けて(どのようにアルゴリズムの中にあります)、ルートノードをT配列に入れて、それから再帰的に左サブツリーと右サブツリーを呼び出して、完全二叉探索木が完成するまで(T配列は完全二叉探索木の層順遍歴である).Cプログラム実装:
#include
#include
#include
using namespace std;
int *A;
int *T;
//
//N
int LNum(int N){
int X,H,min;//X ,H ,min
int L=0;
H=(int)(log(N+1)/log(2));
X=N-pow(2,H)+1;
if(X>pow(2,(H-1))){
min=2^(H-1);
}
if(X<=pow(2,(H-1))){
min=X;
}
L=min+pow(2,(H-1))-1;
return L;
}
//
// a 、 、
void slove(int AL,int AR,int TRoot){
int n;
int L;
int LRoot,RRoot;
n=AR-AL+1;
if(n==0) return;
L=LNum(n);
T[TRoot]=A[AL+L];
LRoot=TRoot*2+1;
RRoot=LRoot+1;
slove(AL,AL+L-1,LRoot);
slove(AL+L+1,AR,RRoot);
}
//
int compare(const void*a,const void*b){
return *(int*)a-*(int*)b;
}
int main(){
int N;
int AL=0;
int TRoot=0;
int temp;
scanf("%d
",&N);
int AR=N-1;
A=(int*)malloc(sizeof(int)*N);//
T=(int*)malloc(sizeof(int)*N);
for(int i=0;iscanf("%d",&temp);
A[i]=temp;
}
qsort(A,N,sizeof(int),compare);
slove(AL,AR,TRoot);
for(int j=0;jprintf("%d ",T[j]);
return 0;
}