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.
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.
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.
10 1 2 3 4 5 6 7 8 9 0
6 3 8 1 5 7 9 0 2 4
这道题十分巧妙，当BST是完全二叉树时，它的数组存储即满足层序遍历。
思路为对数组表示的二叉树进行中序遍历，并按从小到大的顺序填入数组，最后顺序输出即为层序遍历。
#include<cstdio> #include<algorithm> using namespace std; int n,index=0; int a[1010]; int b[1010]; void inorder(int x){ if(x>n) return; inorder(2*x); b[x]=a[index++]; inorder(2*x+1); } int main(){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); inorder(1); for(int i=1;i<=n;i++){ printf("%d",b[i]); if(i<n) printf(" "); } return 0; }
最后附上我之前自己写的递归，代码存在死循环问题，但vs过期了，没有调试排错，留到以后解决
#include<cstdio> #include<algorithm> #include<queue> #include<cmath> using namespace std; int a[1010]; int b[15]; int n; struct node{ int data; node *left,*right; }*Node; node* change(int num,int l,int r){ sort(a+l,a+r+1); if(num==0) return NULL; node *root=new node; int t=0,now=num-1; if(now==0){ root->data=a[l]; root->left=root->right=NULL; return root; } while(now>2*b[t]) t++; if(now>=b[t]+b[t-1]){//zuoman root->data=a[l+b[t]]; root->left=change(b[t],l,l+b[t]-1); root->right=change(num-b[t]-1,l+b[t]+1,r); printf("%d\n",root->data); return root; }else{//zuoweiman root->data=a[r-b[t-1]]; root->left=change(num-b[t-1]-1,l,r-b[t-1]-1); root->right=change(b[t-1],r-b[t-1]+1,r); return root; } } void bfsprint(node *r){ queue<node*> q; q.push(r); int tt=0; while(!q.empty()){ node *f=q.front(); q.pop(); printf("%d",f->data); if(++tt<n) printf(" "); if(r->left!=NULL) q.push(r->left); if(r->right!=NULL) q.push(r->right); } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=0;i<=15;i++) b[i]=pow(2,i)-1; Node=change(n,1,n); //bfsprint(Node); return 0; }
1064 Complete Binary Search Tree （BST+CBT）
原文：https://www.cnblogs.com/exciting/p/10427028.html