1064. Complete Binary Search Tree

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

基本思路是：先对输入的数进行非递减排序，排序之后，创建一棵空的完全二叉树，按中序遍历填充依次将数组中的元素填充到树中，因为二叉搜索树的中序遍历就是按元素值从小到大的排序。完成后再层序遍历一次。 程序代码：

#include<cstdio> #include<cstdlib> #include<iostream> #include<queue> #define MAX 1001 using namespace std; typedef struct node { int data; struct node* left; struct node* right; }node; node* creat(node a[],int n); int m=1; void InOrderSet(node* s,int num[],int* i); void InOrderVisit(node* s); void levelTravel(node* root); int comp(const void* a,const void* b); int main() { node a[MAX]; int num[MAX]; int n; scanf("%d",&n); int i=0; for(i=1;i<=n;i++) { scanf("%d",&num[i]); } qsort(&num[1],n,sizeof(int),comp);//排序 creat(a,n);//创建空树 InOrderSet(&a[1],num,&m);//中序遍历填充树 levelTravel(&a[1]);//层序遍历树 return 0; } node* creat(node a[],int n)//创建n个节点的空完全二叉树 { int i=1; if(n%2==0) { while((i*2+1)<=n) { a[i].left = &a[i*2]; a[i].right = &a[i*2+1]; i++; } a[i].left=&a[i*2]; a[i].right=NULL; i++; while(i<=n) { a[i].left = NULL; a[i].right = NULL; i++; } } else { while((i*2)<=n) { a[i].left = &a[i*2]; a[i].right = &a[i*2+1]; i++; } while(i<=n) { a[i].left = NULL; a[i].right = NULL; i++; } } return &a[1]; } void InOrderSet(node* s,int num[],int* i)//按中序遍历顺序填充完全二叉树 { if(s==NULL) return; else { InOrderSet(s->left,num,&m); s->data = num[m++]; InOrderSet(s->right,num,&m); } } /*void InOrderVisit(node* s) { if(s==NULL) return; else { InOrderVisit(s->left); printf("%d ",s->data); InOrderVisit(s->right); } }*/ void levelTravel(node* root) //层序遍历 { queue<node> s; s.push(*root); node p; while(!s.empty()) { p = s.front(); s.pop(); cout<<p.data; if(p.left!=NULL) s.push(*(p.left)); if(p.right!=NULL) s.push(*(p.right)); if(!s.empty()) cout<<' ';//避免在行末添加空格 } } int comp(const void* a,const void* b)//供qsort函数使用的比较函数 { return *(int*)a-*(int*)b; }