PTA 04-树6 Complete Binary Search Tree（建立完全二叉搜索树+中序遍历建树+层次遍历）...
大体思路：
1.选取数据结构来建树：如果用链表实现，层次遍历需要队列辅助；如果用数组实现，可以直接顺序输出（i作为根节点，2i就是左节点，2i+1就是右节点，i=1,2,3......）。所以使用数组来表示cbst
2.对key值进行非降序排序，然后根据ldr建树
3.层次遍历输出
本题get到一个新姿势：
对bst中序遍历（ldr）=从小到大输出键值
根据这个姿势，我们可以依据ldr来建树（只适用于数组实现，基于链表实现的话，需要找父亲节点，相对麻烦），代码如下：
void ldr(int root) { if(root>n) return; else { ldr(2*root); cbst[root]=node[k++];//最初的ldr写法到这应该是输出节点key，我们将其改为存储，这样我们就可以成功建树了！ ldr(2*root+1); } }
基于数组实现的层次遍历，只需要对数组进行顺序输出即可，代码：
void levelTraverse(int root) { for(int i=root;i<=n;++i) printf("%d%c",cbst[i]," \n"[i==n]); }
总体代码：
#include <bits/stdc++.h> using namespace std; int n, k=1, cbst[1005], node[1005]; void ldr(int root) { if(root>n) return; else { ldr(2*root); cbst[root]=node[k++]; ldr(2*root+1); } } void levelTraverse(int root) { for(int i=root;i<=n;++i) printf("%d%c",cbst[i]," \n"[i==n]); } int main() { cin>>n; for(int i=1;i<=n;++i) cin>>node[i]; sort(node+1, node+1+n); int root=1;ldr(root); levelTraverse(root); return 0; }