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

========================================
翻译过来就是…完全二叉搜索树
两个特征：二叉搜索树+完全二叉树
后面的代码里面可能有一点冗余的地方，就是那个if里面的，不过运行结果不影响，就没去改了。
我想的办法是自顶向下的，从一堆排好序的数中揪出那个“中间的”，然后分为两棵子树做，如此迭代(具体输出用<queue>的数组一层层弄就行了，这边懒得写)：

function foo:
本行完整的应有m = log2(N)个
本行多出的有r = N – m个 （就是完全树的最底下一行多余的节点数）
if r==0:
太完美了..将中间的数找出，放入输出队列中
else:
最后一排填满的话会有k=2^m个元素
那么左右边分开的话，各有k/2个
这样就能算出左边右边应该有多少个元素“多余”，去除左右边多余的剩下就是真正的长度
去除多余的元素，根据长度找出中间的元素，放入输出队列
递归接着算

=======================================================================

#include
#include /* qsort */
#include
#include
using namespace std;
int compare(const void *a, const void *b)
{
return ( *(int*)a - *(int*)b);
}
queue *results;
void run(int* srcAry, int fromIndex, int toIndex, int level)
{
int length = toIndex - fromIndex + 1;
if(length < 1) return; if(length == 1) { //到底了 //printf("%d ", srcAry[fromIndex]); results[level].push(srcAry[fromIndex]); return; } int m = log((double)length)/log((double)2); int r = length - pow(2.0f,m) + 1; if(r == 0) { int midIndex = fromIndex + length/2; //printf("%d ", srcAry[midIndex]); results[level].push(srcAry[midIndex]); run(srcAry, fromIndex, midIndex-1, level-1); run(srcAry, midIndex+1, toIndex, level-1); } else { int k = pow(2.0f, m); int left = k/2, right = k/2; if(r <= left) { //只有左边有 left = r; right = 0; } else { //右边也有 right = r - left; } int restLength = length - r; int midIndex = fromIndex + left + restLength/2; //printf("%d ", srcAry[midIndex]); results[level].push(srcAry[midIndex]); run(srcAry, fromIndex, midIndex -1, level-1); run(srcAry, midIndex+1, toIndex, level-1); } } int main() { int N; scanf("%d", &N); int *ary = new int[N]; for(int i=0; i[level +1];
run(ary, 0, N-1, level);
int count = 1;
level++;
while (level--)
{
queue q = results[level];
while(!q.empty())
{
printf("%d", q.front());
if(count < N) printf(" "); count ++; q.pop(); } } return 0; }