图之完全二叉搜索树C语言

• 什么是完全二叉搜索树？
  

• 基本思路

  • 这里采用数组，因为是完全二叉树，所以不会浪费空间，树的层序遍历就是数组的顺序输出，所以这里用数组比链表更合适
  • 需要先将放结点数组T【】升序排好序，根据结点总数求出完全二叉树根结点的左子树的个数假设是 i 个，那么根结点就是第 i 个结点即R【0】=T【i】，然后递归的求解左右子树即可
    
    如上图，左子树有6个结点，所以R【0】=6；再求左子树的左子树的结点个数为3，所以R【1】=3；以此类推

• 代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int T[10]={0,1,2,3,4,5,6,7,8,9};//已经排好序
int R[10]={0};
//根据总的结点个数求左子树的结点个数
int GetLeftLength(int n)
{
	double t=log(n+1)/log(2);
	int h=(int)t;
	int x=n-(pow(2,h)-1);
	if(x>pow(2,h-1))	x=pow(2,h-1);
	int l=pow(2,h-1)-1+x;
	return l;
 }
 //创建完全二叉搜索树
void CreateWqSearchBinTree(int left,int right,int root)
{
	int n=right-left+1;
	if(n==0)	return;
	int l=GetLeftLength(n);
	R[root]=T[left+l];
	int Lroot=2*root+1;
	int Rroot=Lroot+1;
	CreateWqSearchBinTree(left,left+l-1,Lroot);
	CreateWqSearchBinTree(left+l+1,right,Rroot);
}
int main(int argc, char** argv) {
	CreateWqSearchBinTree(0,9,0);
	for(int i=0;i<10;i++)	printf("%d ",R[i]);
	return 0;
}

• 运行结果