欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

创建一棵完全二叉搜索树

程序员文章站 2024-03-20 10:16:10
...

题目大意:给出一组不超过1000个的序列,生成一棵完全二叉搜索树并层序输出

算法思路:

       1、由于是创建一棵完全二叉树,结点从上至下从左至右与数组下标相同,于是建树采用数组形式

       2、对给出的一组无序序列从小到大排序,得到arr[ ]

       3、根据二叉搜索树的性质,某一结点的左子树都小于该结点,右子树都大于该结点,根据完全二叉树的性质,给定一个固定大小的结点总数n,就可以计算出根结点左子树的结点总数x,于是有序序列arr的前x个就是左子树,第x+1就是根结点,剩下的就是右子树。

      4、从根结点开始对数列递归划分,得到完全二叉搜索树T[ ],顺序输出就得到层序遍历的结果

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int arr[maxn],T[maxn];

//获取有n个结点的完全二叉树左子树的个数
int getLeftLength(int n){
    //不包括叶子结点的完美二叉树的高度
	int height = floor(log(n+1)/log(2)); 
    //完全二叉树第height+1层的结点数,也就是叶子节点数   
	int x = n + 1 - pow(2,height); 
    //取min(叶子节点数,叶子节点数的一半)
	x = min(x,(int)pow(2,height-1));
    //返回左子树的结点个数
	return ((int)pow(2,height-1))- 1 + x;
}

//处理arr[ALeft,ARight]序列
//初始调用solve(0,n-1,0)
void solve(int ALeft, int ARight, int TRoot){
    //要处理的结点数n
	int n = ARight - ALeft + 1;
    //递归终止条件
	if(n == 0) return;
    //当前序列中根结点左子树的结点个数
	int L = getLeftLength(n);
    //用来存储完全二叉搜索树的序列数组T,当前序列中根结点的值arr[ALeft + L]
	T[TRoot] = arr[ALeft + L];
    //根据完全二叉树的性质,TRoot的左孩子下标为TRoot*2 + 1 (根结点下标从0开始)
	int LeftTRoot = TRoot*2 + 1;
	int RightTRoot = LeftTRoot + 1;
    //递归处理左子树
	solve(ALeft,ALeft+L-1,LeftTRoot);
    //递归处理右子树
	solve(ALeft+L+1,ARight,RightTRoot);
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0; i<n; i++) scanf("%d",&arr[i]);
	sort(arr,arr+n);
	solve(0,n-1,0);
	for(int i=0; i<n; i++){
		if(i) printf(" ");
		printf("%d",T[i]);
	}
	return 0;
}