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. Each input file contains one test case. For each case,the first line contains a positive integer?N?(≤). 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:
Sample Output:
?
?
?
1 #include <cstdio>
2 #include <math.h>
3 #include <algorithm>
4
5 using namespace std;
6
7 int a[1010];
8 int T[1010];
9
10 int GetLeftLength(int n)
11 {
12 int H=log(n+1)/log(2);
13 int X=n+1-pow(2,H);
14 if(X>pow(2,H-1))
15 X=pow(2,H-1);
16 int L=pow(2,H-1)-1+X;
17 return L;
18 }
19
20 void solve(int ALeft,int ARight,int TRoot)
21 {
22 int n=ARight-ALeft+1;
23 if(n==0) return;
24 int L=GetLeftLength(n);
25 T[TRoot]=a[ALeft+L];
26 int LeftTRoot=TRoot*2+1;
27 int RightTRoot=LeftTRoot+1;
28 solve(ALeft,ALeft+L-1,LeftTRoot);
29 solve(ALeft+L+1,ARight,RightTRoot);
30 }
31
32 int main()
33 {
34 int n;
35 scanf("%d",&n);
36 for(int i=0;i<n;i++)
37 {
38 scanf("%d",&a[i]);
39 }
40 sort(a,a+n);
41 solve(0,n-1,0);
42 for(int i=0;i<n;i++)
43 {
44 if(i==0)
45 printf("%d",T[i]);
46 else printf(" %d",T[i]);
47 }
48 return 0;
49 }
(编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|