大致题意就是给出一个包含 N个非负整数的序列，然后构造出一个完全二叉查找树。
思路：
一，因为二叉查找树的中序遍历序列是递增序列，所以对给出的序列进行递增排序。
二，因为完全二叉树可以通过一维数组CBT存放，且满足下面三个性质：
1，根结点下标为1；
2，当前根结点root的左孩子下标是root*2，右孩子下标是root*2+1;
3，当 当前根结点下标 root 大于 元素个数 N时，表示 是空结点。
所以可以在对完全二叉树CBT进行中序遍历时，往CBT中一个一个的插入元素。
三，顺序输出一维数组CBT，即为层序遍历序列。
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 5 const int maxn = 2000; 6 int n,in[maxn] = {0},CBT[maxn] = {0},index = 0; 7 void inorder(int root) { //中序遍历完全二叉树 8 if(root > n) return ;//空结点，直接返回 9 inorder(root*2); //往左子树递归 10 CBT[root] = in[index++]; 11 inorder(root*2+1);//往右子树递归 12 } 13 14 int main() { 15 cin>>n; 16 for(int i = 0; i < n; ++i) 17 cin>>in[i]; 18 sort(in,in+n); 19 inorder(1); //完全二叉树的根结点下标必须是 1 20 for(int i = 1; i<= n; ++i) { 21 if(i > 1) printf(" "); 22 printf("%d",CBT[i]); 23 } 24 return 0; 25 }
ps:
1，我一开始打算根据中序序列，和完全二叉树的性质，用中序遍历的方式构造出一棵二叉链表结构的完全二叉树，后来发现不可能~~
目前，我只能通过先序遍历的方式才能构造出一棵二叉链表结构的二叉树。
2，这是我第二次对 用一维数组表示的完全二叉树 进行中序遍历和层次遍历，，，并且两次做这道题，都没做出来~还是不熟啊~
1064 Complete Binary Search Tree
原文：https://www.cnblogs.com/keep23456/p/12403799.html