pat04-树8. Complete Binary Search Tree (30)

04-树8. Complete Binary Search Tree (30)

时间限制

100 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

CHEN, Yue

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 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<queue>
 6 #include<vector>
 7 #include<cmath>
 8 #include<string>
 9 using namespace std;
10 int tree[1005],endtree[1005];
11 int GetLeftLength(int n){
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     }
17     return x+pow(2,h-1)-1;
18 }
19 void solve(int left,int right,int root){
20     int n=right-left+1;
21     if(!n) return;
22     int l=GetLeftLength(n);
23     endtree[root]=tree[left+l];
24     solve(left,left+l-1,root*2+1);
25     solve(left+l+1,right,root*2+2);
26 }
27 int main(){
28     //freopen("D:\INPUT.txt","r",stdin);
29     int n;
30     scanf("%d",&n);
31     int i;
32     for(i=0;i<n;i++){
33         scanf("%d",&tree[i]);
34     }
35     sort(tree,tree+n);
36     solve(0,n-1,0);
37     printf("%d",endtree[0]);
38     for(i=1;i<n;i++){
39         printf(" %d",endtree[i]);
40     }
41     printf("
");
42     return 0;
43 }

方法二：

链表做法：

递归建树的思想：想找出当前的中间大的树，作为当前树根，然后遍历左子树，右子树，最后对所建的BST进行层序遍历。

当前元素总个数为n，则层数k为ceil(log2(n+1))：

1.n>=3*2^(k-2)，即查找树的最后一个元素位于根的右子树部分。则此时右子树有 n-(3*2^(k-2)-1)+2^(k-2)-1 个元素，左边有 n-右子树元素个数-1=n-(n-(3*2^(k-2)-1)+2^(k-2)-1)-1=2^(k-1)-1个元素，则中间元素下标为 2^(k-1)-1 （从0开始）。

2.n<3*2^(k-2)，即查找树的最后一个元素位于根的左子树部分。则此时右子树有 2^(k-2)-1 个元素，左边有 n-右子树元素个数-1=n-(2^(k-2)-1)-1=n-2^(k-2) 个元素，则中间元素下标为 n-2^(k-2) （从0开始）。

 1 #include<cstdio>
 2 #include<functional>
 3 #include<queue>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<iostream>
 7 using namespace std;
 8 int mem[1005];
 9 struct node{
10     int v;
11     node *l,*r;
12     node(){
13         l=r=NULL;
14     }
15 };
16 void CBTBuild(int *mem,int n,int mid,node *&p){
17     //q.push(mem[mid]);
18     p=new node();
19     p->v=mem[mid];
20     //cout<<mem[mid]<<endl;
21 
22     if(mid-1>=0){//left tree
23         int nn=mid;
24         int k=ceil(log(nn+1)/log(2));
25         if(nn>=3*pow(2,k-2)){//超过一半
26             CBTBuild(mem,nn,pow(2,k-1)-1,p->l);
27         }
28         else{//未超过一半
29             CBTBuild(mem,nn,nn-pow(2,k-2),p->l);
30         }
31     }
32     if(mid+1<n){//right tree
33         int nn=n-(mid+1);
34         int k=ceil(log(nn+1)/log(2));
35         if(nn>=3*pow(2,k-2)){//超过一半
36             CBTBuild(mem+mid+1,nn,pow(2,k-1)-1,p->r);
37         }
38         else{//未超过一半
39             CBTBuild(mem+mid+1,nn,nn-pow(2,k-2),p->r);
40         }
41     }
42 }
43 int main(){
44     //freopen("D:\INPUT.txt","r",stdin);
45     int n,i,j,k;
46     queue<node> q;
47     scanf("%d",&n);
48     for(i=0;i<n;i++){
49         scanf("%d",&mem[i]);
50     }
51     sort(mem,mem+n);
52 
53     /*for(i=0;i<n;i++){
54         cout<<mem[i]<<endl;
55     }*/
56     node *h;
57     k=ceil(log(n+1)/log(2));
58     if(n>=3*pow(2,k-2)){//超过一半
59         CBTBuild(mem,n,pow(2,k-1)-1,h);
60 
61         //cout<<mem[int(pow(2,k-1)-1)]<<endl;
62 
63     }
64     else{//未超过一半
65         CBTBuild(mem,n,n-pow(2,k-2),h);
66 
67         //cout<<mem[int(n-pow(2,k-2))]<<endl;
68 
69     }
70     int top;
71     node p=*h;
72     q.push(p);
73     printf("%d",p.v);
74     while(!q.empty()){
75         p=q.front();
76         q.pop();
77         if(p.l!=NULL){
78             q.push(*(p.l));
79             printf(" %d",p.l->v);
80         }
81         if(p.r!=NULL){
82             q.push(*(p.r));
83             printf(" %d",p.r->v);
84         }
85     }
86     printf("
");
87     return 0;
88 }