1064. Complete Binary Search Tree (30)
  

   

    

     时间限制
    
    

     100 ms
     

    
   
   

    

     内存限制
    
    

     65536 kB
     

    
   
   

    

     代码长度限制
    
    

     16000 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
   
N个结点，无序；
   
要求获得 左<中<=右的完全二叉树
   
首先输入sort排序非降#include<algorithm>
   
接着buildCBTreeDFS(CompleteBinarySearchTree*CBT, int STar ,int END_1)构建好完全二叉树，当前数组序号从STar到END_1；这里有len=END_1-STar+1个元素，
   
难点一int GETrightCount( int len)根据长度len获得这些子结点  组建成  子完全二叉树 右边的结点个数  并返回；
   
然后通过END_1-GETrightCount(len)获得root；
   
难点二：递归调用停止判断；
   
接着利用queue 先进先出#include<queue>  输出
   


   

  
评测结果
  

测试点

#include<iostream>   
#include<algorithm>
#include<queue>
using namespace std;
#define NOTNEXTNODEs -1
struct CompleteBinarySearchTree
{
  int value;
  int left_index;
  int right_index;
};
int Log2_myself(int n)
{
  int index = 0;
  while (n > 0)
  {
    n=n >> 1;
    index++;
  }
  return index;
  /*n=n >> 1相当于n>>=1相当于n/2;
  这里整个函数相当于求log2(n)；也可以用下面的
  #include<math.h> (int)(log(x*1.0) / log(2.0))+1;*/
}
int pow_myself(int index,int radix)
{
  int i,temp=index;
  for (i = 1; i < radix; i++)
    temp*= index;
  return temp;/*#include<math.h>pow(index, radix)
         等于index的radix次方*/
}
void Dureadln(CompleteBinarySearchTree*CBT,int N)
{
  for (int index = 0; index < N; index++)
  {
    cin >> CBT[index].value;
    CBT[index].left_index = CBT[index].right_index = NOTNEXTNODEs;
  }
}
bool CBTCMp(const CompleteBinarySearchTree&A, const CompleteBinarySearchTree&B)
{
  return A.value < B.value;
}
int GETrightCount( int len)
{ 
  int level,lcount,lastfull;
  level = Log2_myself(len); 
  lcount = pow_myself(2, level); 
  lastfull = lcount / 2; 
  if (lastfull/2 < len - lcount/2+1) 
    return  len - lcount / 2; 
  return lastfull / 2-1;
}
int buildCBTreeDFS(CompleteBinarySearchTree*CBT, int STar ,int END_1)
{
  int root =END_1- GETrightCount(END_1-STar+1);   
  CBT[root].left_index = root >STar ? buildCBTreeDFS(CBT, STar, root-1) : NOTNEXTNODEs; 
  CBT[root].right_index = root < END_1 ? buildCBTreeDFS(CBT, root + 1, END_1) : NOTNEXTNODEs; 
  return root; 
}
void printfCBT(int root, CompleteBinarySearchTree*CBT)
{
  queue<int>index;
  int size,newroot;
  index.push(root);
  cout << CBT[root].value;
  while (!index.empty())
  {
    size = index.size();
    while (size--)
    {
      root = index.front();
      index.pop();
      if (CBT[root].left_index != NOTNEXTNODEs)
      {
        newroot = CBT[root].left_index;
        cout <<" "<< CBT[newroot].value;
        index.push(newroot);
      }
      if (CBT[root].right_index!= NOTNEXTNODEs)
      {
        newroot = CBT[root].right_index;
        cout << " " << CBT[newroot].value;
        index.push(newroot);
      }
    }
  }
  cout << endl;
}
int main()
{
  CompleteBinarySearchTree*CBT;
  int N;
  cin >> N;
  CBT= new CompleteBinarySearchTree[N]; 
  Dureadln(CBT, N);
  sort(CBT, CBT + N,CBTCMp); 
  printfCBT(buildCBTreeDFS(CBT, 0,N-1),CBT);
  delete[]CBT;
  system("pause");
  return 0;
}