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????????这题的思路其实非常简单，问题在于如何简洁的实现。
????????思路其实是：将输入的一堆数据按照升序排列好之后，计算得到左子树的结点个数后，因为所有左子树结点值都小于根结点，所有右子树结点值都大于或等于根结点，那么在排好的序列中左子树个数+1的那个数肯定就是根结点。
????????那么怎么得到左子树的结点数呢，因为这又是完全二叉树，其有很多特殊性质：
1、层数为log2N（N为结点数）
3、每层的结点数最大为2^（k-1）（k为第几层）
3、前k层的总的结点数为2^k - 1
????????完全二叉树除了叶结点不满以外，其它应该都是满的，而叶结点也是从左到右排布的，中间没有空的，那么如图：
? ? ? ? ?至于思路的实现，可以链表，也可以数组，但我个人认为数组会更简单，因为涉及层次遍历。并且用一组从小到大排好的数来构造完全二叉搜索树，如果用链表，会非常麻烦。
#include<stdio.h>
#include<algorithm> ? ?//sort函数?
#include<cmath> ? ? ? ? ?//pow函数?
#include<vector> ? ? ? //sort函数，和algorithm一起才能使用sort?
#define Maxsize 2005
using namespace std;int num[Maxsize], BST[Maxsize];
int Find_Left_Node(int N);
void Find_root(int left, int right, int root );int main()
{
?? ?int N=0, i=0, Data=0; ??
?? ?scanf("%d", &N);
?? ?for(i=0;i<N;i++) scanf("%d", &num[i]);
?? ?sort(num,num+N);
?? ?Find_root(0, N-1, 0);
?? ?for(i=0;i<N;i++){
?? ??? ?printf("%d", BST[i]);
?? ??? ?if(i!=N-1) printf(" ");
?? ?}
?? ?
?? ?return 0;
}int Find_Left_Node(int N)? ? ? ?//计算左子树结点个数
{
?? ?int i=0, L=0, floor=0, sum=1,tmp=0, number=0;
?? ?for(i=0;sum<=N+1;i++){
?? ??? ?sum*=2;
?? ?}
?? ?floor=i;
?? ?sum = (int) pow(2,floor-1);
?? ?number=N-(sum-1);
?? ?tmp=(int) pow(2, floor-2);
?? ?L=number<tmp?number:tmp;
?? ?L=L+(sum-2)/2;
?? ?
?? ?return L;
}void Find_root(int left, int right, int root )? ? ? ?
//递归将大序列分成一堆子序列，分别求左子树结点个数
{
?? ?int length=right-left+1;
?? ?if(!length) return;
?? ?int L=Find_Left_Node(length);
?? ?BST[root]=num[left+L];
?? ?int leftroot=2*root+1;
?? ?int rightroot=leftroot+1;
?? ?Find_root(left,left+L-1,leftroot);
?? ?Find_root(left+L+1,right,rightroot);
}