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 这道题考察的点是二叉搜索树和完全二叉树。刚开始我第一反应就是完全二叉树的性质：用数组存储的话，父节点下标为i,左孩子为2i，右孩子为2i+1。而一个完全二叉搜索树的最小节点肯定在最左边。我一开始的想法是用数组存储，找到最左边那个位置，放进去0，然后找到0的父节点，放1，再放右节点的2，再往上一直放，但是当时没想到用递归，觉得这样写会很麻烦，所以放弃了。
接着我用了最普通的链式方法建树，然后层序遍历输出。不得不说，链式方法建树很繁琐，我调试了很久才通过。具体思路是，先把输入数据放在一个vector里面，然后排序，从小到大排。然后找出整个树的根节点的下标（找的方法是先计算左子树有几个节点），再递归，在左子树再建树。这样非常麻烦，写递归的时候很容易出错。
后来AC之后在网上搜了搜，发现有非常好的做法。其实我一开始的想法类似，但是没有更进一步去想。一个完全二叉搜索树的中序遍历的结果就是递增排列的，那么我们采用中序遍历的方法去建树(即遍历的时候，visit操作是给节点赋值！)。这种逆向思维是我之前完全没想到的，这次学习了。总之就是，采用中序遍历的方法，利用完全二叉树的父子节点关系去建树，最后把数组按序输出即可。
下面我把两种方法的代码都贴上来。很明显，第一段代码明显比第二段简单得多得多得多得多！！！
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std; int N;
int pos=;
int *tree;
vector<int> vec; void build(int n)
{
if (n>N) return;
else
{
build(n*);
tree[n] = vec[pos++];
build(n*+);
}
} int main()
{
int element;
cin >> N;
tree = new int [N+];
//输入元素并排序
for (int i=;i<N;i++)
{
cin >> element;
vec.push_back(element);
}
sort(vec.begin(),vec.end()); build();
cout << tree[];
for (int i=;i<=N;i++)
cout << ' ' << tree[i];
return ;
}
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; typedef struct node* tree;
struct node
{
int data;
tree left;
tree right;
}; tree BuildTree (tree,int,unsigned,unsigned);
int FindRoot(int,int);
void LevelOrderTraversal(tree T);
vector<int> vec; int main()
{
int N,element;
cin >> N; //输入元素并排序
for (int i=;i<N;i++)
{
cin >> element;
vec.push_back(element);
}
sort(vec.begin(),vec.end()); unsigned b=,e=vec.size()-; int root=FindRoot(N,);
tree T = nullptr;
T=BuildTree(T,root,b,e); LevelOrderTraversal(T); return ;
} int FindRoot(int N,int base)
{
int level=int(log(double(N))/log(2.0))+; //共有这么多层
int root=;
if (N == )
root = ;
else if (N == )
root = ;
else if (N==)
root = ;
else
if (N-(pow(double(),double(level-))-) > pow(double(),double(level-)) )//左子树满了
root = pow(double(),double(level-))-;
else
root = pow(double(),double(level-))-+N-(pow(double(),double(level-))-);
return root+base;
} tree BuildTree(tree T,int root,unsigned b,unsigned e)
{
//cout << b << e << endl;
if (e==b)
{
T=new node;
T->data = vec[b];
T->left = nullptr;
T->right = nullptr;
}
else
{
T = new node;
T->data = vec[root];
T->left = BuildTree(T,FindRoot(root-b,b),b,root-);
if (e!=root)
T->right= BuildTree(T,FindRoot(e-root,root+),root+,e);
else
T->right = nullptr;
}
return T;
} void LevelOrderTraversal(tree T)
{
bool flag=true;
queue<tree> Q;
if (!T) return;
Q.push(T);
while (!Q.empty())
{
if (flag)
{
cout << Q.front()->data;
flag = false;
}
else
cout << ' ' << Q.front()->data;
if (Q.front()->left)
Q.push(Q.front()->left);
if (Q.front()->right)
Q.push(Q.front()->right);
Q.pop();
}
}