PATA1064 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:

1
2
10
1 2 3 4 5 6 7 8 9 0

Sample Output:

1
6 3 8 1 5 7 9 0 2 4

题目大意:
给出N个权值,由它们创建一棵完全二叉查找树,输出层序遍历
思路:
基于二叉查找树的特性:中序遍历为非递减有序。可以先将序列从小到大排序,而后对一棵空的完全二叉树1~N进行中序遍历,将权值序列中的数依次填入。最后按完全二叉树的下标依次输出即为其层序遍历序列。(注意:此题中我是按下标从1开始记的,从0开始的话要相应更改完全二叉树左右子树的下标表示式)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n,cnt=0;
vector<int> in,bst;
void inorder(int root){
if(root>n) return;
inorder(2*root);
cnt++;
bst[root]=in[cnt];
inorder(2*root+1);
}
int main(){
scanf("%d",&n);
in.resize(n+1);
bst.resize(n+1);
for(int i=1;i<=n;i++)
scanf("%d",&in[i]);
sort(in.begin()+1,in.end());
inorder(1);
printf("%d",bst[1]);
for(int i=2;i<=n;i++)
printf(" %d",bst[i]);
return 0;
}