1064 Complete Binary Search Tree (30分)
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、左子结点权值小于其父结点的权值
2、右子结点权值大于其父结点的权值
3、每个左右子结点都是二叉搜索树
输入:第一行n表示结点个数,第二行表示结点的权值。
输出:输出其层序遍历的结果
解题思路:不需要建树。先将各个结点的权值保存到数组中,接着将数组从小到大排序,以便放入正确的层序遍历数组中。通常将树放入数组中时,都会牺牲0号索引,从索引1开始存储。用递归算法就能获得层序遍历的结果,接下来利用题目给出的例子分析下这个递归算法。
样例构建出来的树长这样:
根据上图,可得到层序遍历数组:
index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
num | 6 | 3 | 8 | 1 | 5 | 7 | 9 | 0 | 2 | 4 |
现在模拟递归算法的过程:
n = 10
-
root = 1,root<=n为true,进入if语句中---后续还未完成
-
执行get_level(root*2),即get_level(1*2),root=2,root<=n为true,进入if语句中---后续还未完成
-
执行get_level(root*2),即get_level(2*2),root=4,root<=n为true,进入if语句中---后续还未完成
-
执行get_level(root*2),即get_level(4*2),root=8,root<=n为true,进入if语句中---后续还未完成
-
执行get_level(roo*2),即get_level(8*2),root=16,root<=n为false!步骤 5)执行完毕。返回上一条语句,即步骤 4),执行未完成的部分。
这时,步骤5) 返回到 步骤 4) 的后续执行步骤,root=8且c=0,level[root]=v[c++]即level[8]=v[0],且c=1。
-
接着往下执行,root = 8, get_level(root*2+1),即get_level(8*2+1)---步骤6)只是个过渡,已完成。
-
get_level(17),root = 17,root<=n为false!步骤7) 执行完毕。至此,步骤4才真正执行完毕。返回上一条语句,即步骤 3),执行未完成的部分。
这时,步骤7) 返回到 步骤3) 的后续执行步骤,root=4且c=1,level[root]=v[c++]即level[4]=v[1],且c=2。
-
接着往下执行,root = 4,get_level(root*2+1),即get_level(4*2+1)---步骤8)只是个过渡,已完成。
-
get_level(9),root = 9,root<=n为true,进入if语句中---后续还未完成
-
执行get_level(root*2),即get_level(9*2),root=18,root<=n为false!步骤10) 执行完毕。返回到上一条语句,即步骤9),执行未完成部分
这时,步骤10) 返回到 步骤 9)的后续执行步骤,root=9且c=2,level[root]=v[c++]即level[9]=v[2],且c=3。
-
接着往下执行,root = 9,get_level(root*2+1),即get_level(9*2+1)---步骤11)只是个过渡,已完成。
-
get_level(19),root = 19,root<=n为false!至此,步骤 9)执行完毕,步骤3)也执行完毕。---步骤12)只是个过渡,已完成。
-
步骤12) 执行完比后,会返回上一个为执行完成的步骤,即步骤2),往后以此类推。。。
上述过程写的看似复杂,但是自己动手把数据带入进去,模拟一下就也就那么回事,不难不难。
#include<bits/stdc++.h>
using namespace std;
int n, c=0;
vector<int> level, v;
void get_level(int root){
if(root<=n){
get_level(root*2);
level[root] = v[c++];
get_level(root*2+1);
}
}
int main()
{
scanf("%d", &n);
v.resize(n);
level.resize(n+1);
for(int i=0; i<n; i++){
scanf("%d", &v[i]);
}
sort(v.begin() ,v.end());
get_level(1);
for(int i=1; i<=n; i++){
if(i!=1) printf(" ");
printf("%d", level[i]);
}
return 0;
}