04-树6 Complete Binary Search Tree(浙大数据结构PTA习题）

04-树6 Complete Binary Search Tree 分数 30 作者陈越单位浙江大学

Question:

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.

Both the left and right subtrees must also be binary search trees.

A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.

Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input:

10
1 2 3 4 5 6 7 8 9 0

Sample Output:

6 3 8 1 5 7 9 0 2 4

代码长度限制：16 KB 时间限制：400 ms 内存限制：64 MB

题目解析：

题目大意：给定一系列结点，如何构建一棵二叉搜索完全树（即既满足二叉搜索树的性质又满足完全二叉树的性质），并最后要求对这棵二叉搜索完全树进行层序遍历。

关键点1：通过给定结点构造出一棵完全二叉搜索树

若结点总数量给定，那么根据完全二叉树的性质，我们可以得到其根结点左子树的结点个数和根结点右子树的结点个数；进一步，若结点按照有序（比如非递减）排列，那么根据根结点左子树的结点个数（或右子树的结点个数）和二叉搜索树的性质，我们就可以确定根结点的位置。

关键点2：实现对完全二叉搜索树的层序遍历

借助队列实现。

参考代码：

# include<stdio.h>
# include<stdlib.h>
# include<math.h>
# define MAXNODE 1000

typedef struct TreeNode* CBST;
struct TreeNode{
	int Data;
	CBST Left;
	CBST Right;
}; 

void Swap(int* a, int* b);
void InsertSort(int Array[],int N);
CBST FindRoot(int Array[],int left,int right);
void LayerSort(CBST);

int main(){
	// 接收一个数组
	int N;
	scanf("%d",&N);
	int Array[N];
	int i;
	for(i=0;i<N;i++){
		scanf("%d",&Array[i]);
	}
	// 对一个数组进行插入排序 
	InsertSort(Array,N);
	// 构建完全二叉搜索树
	CBST tree = FindRoot(Array,0,N-1);
	// 对完全二叉搜索树进行层序遍历
	LayerSort(tree);
	
	return 0;
}

// 对一个完全二叉搜索树进行层序遍历
void LayerSort(CBST tree){
	// 创建一个队列用于输出
	CBST Array[MAXNODE];
	int Head=-1, Rear=-1;
	// 压入根结点数据 
	Array[++Rear] = tree; 
	while(Head!=Rear){
		// 出队一个结点，并分别压入其左右结点(若不为空)
		if(Head==-1)printf("%d",Array[++Head]->Data);
		else printf(" %d",Array[++Head]->Data);
		if(Array[Head]->Left!=NULL)Array[++Rear] = Array[Head]->Left;
		if(Array[Head]->Right!=NULL)Array[++Rear] = Array[Head]->Right; 
	} 
	return;
} 

// 从一个有序数组中，找到完全二叉搜索树的根结点，并且通过递归构建这棵树 
CBST FindRoot(int Array[],int left,int right){
	CBST node = (CBST)malloc(sizeof(struct TreeNode)); 
	// 如果数组中只有一个元素，则自身为根结点，直接返回 
	if(left==right){
		node->Data = Array[left];
		node->Left = node->Right = NULL;
		return node;
	} 
	//  首先判断树高多少 
	int height,total_node = right-left+1; 
	for(height=2;total_node>(int)pow(2,height)-1;height++); 
	// 计算最后一层左子树中的元素个数
	int remain_node = total_node - (int)pow(2,height-1)+1;
	if(remain_node>(int)pow(2,height-2))remain_node = (int)pow(2,height-2);
	// 计算左子树总的结点个数，则根结点的下标为left_node(一定要记得加上left，不要以为数组开头下标一直为0)
	int left_node = (int)pow(2,height-2)-1+remain_node+left; 	
	// 完善根结点信息，递归寻求其它子树根结点 
	node->Data = Array[left_node];
	if(left<left_node)node->Left = FindRoot(Array,left,left_node-1); 
	else node->Left = NULL;
	if(right>left_node)node->Right = FindRoot(Array,left_node+1,right);
	else node->Right = NULL;
	return node;
} 

// 对一个数组进行插入排序 
void InsertSort(int Array[],int N){
	int i,j,tmp;
	for(i=1;i<N;i++){
		tmp = i;
		for(j=i-1;j>=0;j--){
			if(Array[tmp]<Array[j]){
				Swap(&Array[tmp],&Array[j]);
				tmp--;
			}else{
				break;
			}
		}
	}
	return;
} 

// 交换两个地址上的值
void Swap(int* a, int* b){
	int tmp = *a;
	*a = *b;
	*b = tmp;
}