PAT甲级 1064 Complete Binary Search Tree（30分）完全二叉搜索树

Solution：

• 题目要求：给一串构成树的序列，已知该树是完全二叉搜索树，求它的层序遍历的序列。
• 总得概括来说，已知中序，可求root下标，可以求出层序。
  （1）因为二叉搜索树的中序满足：是一组序列的从小到大排列，所以只需排序所给序列即可得到中序。
  （2）因为根据完全二叉树的结点数，可以求出它的根结点在中序中对应的下标，要知道根结点在中序中的下标只要知道左子节点的个数即可。
  （3）已知了中序，又可以根据结点数求出根结点的下标，就可以递归求出左右子树的根结点的下标。
  （4）结点的左孩子为2 * i + 1，右孩子2 * i + 2，就可以根据结点下标和中序数组赋值level数组。
  （5）最后输出所有结点的层序数组level。
• 画张图说明吧：

代码如下：

#include<iostream>#include<math.h>#include<vector>#include<algorithm>using namespace std;vector<int>level,in;//level为层序，in为中序voidlevel_order(intleft,intright,intindex){if(left>right){return;}intn=right-left+1;intl=log(n+1)/log(2);// 除了最后一层的层数intleave=n-(pow(2,l)-1);//最后一层的叶子节点数introot=left+(pow(2,l-1)-1)+min((int)pow(2,l-1),leave);// pow(2,l-1)-1是除了root结点所在层和最后一层外，//左子树的结点个数，pow(2,l-1)是l+1层最多拥有的属于根结点左子树的结点个数，//min(pow(2,l-1),leave)是最后一个结点真正拥有的属于根结点左子树上的结点个数level[index]=in[root];level_order(left,root-1,2*index+1);level_order(root+1,right,2*index+2);}intmain(){intn;cin>>n;in.resize(n);level.resize(n);intnum;for(inti=0;i<n;i++){cin>>in[i];}sort(in.begin(),in.end());level_order(0,n-1,0);cout<<level[0];for(inti=1;i<n;i++){cout<<' '<<level[i];}return0;}

更简单的解法：

（1）如果使用数组来存放完全二叉树，那么对完全二叉树当中的任何一个结点（设编号为x，其中根结点编号为1），其左孩子结点的编号一定时2x，而右孩子结点的编号一定时2x+1,。那么就可以开一个数组level[maxn]，其中level[1]~level[n]按层序存放完全二叉树的n个结点，这个数组就存放了一棵完全二叉树。
（2）考虑到对一棵二叉排序树来说，其中序遍历序列是递增的，先将输入的数字从小到大排序，然后对level数组表示的二叉树进行中序排序，并在遍历的过程中将数字从小到大填入数组。

代码如下：

#include<iostream>#include<algorithm>#include<stdio.h>#include<cmath>#include<queue>#include<cstring>#include<vector>#include<stack>#include<map>#defineMAX 1005#defineINF 0x3f3f3f3ftypedeflonglongll;usingnamespacestd;intn,id=0;intin[MAX],level[MAX];voidinorder(introot){//中序遍历if(root>n)return;inorder(root*2);//往左子树递归level[root]=in[id++];//根结点处赋值in[id]inorder(root*2+1);//往右子树递归}intmain(){scanf("%d",&n);for(inti=0;i<n;i++){scanf("%d",&in[i]);}sort(in,in+n);inorder(1);for(inti=1;i<=n;i++){printf("%s%d",i==1?"":" ",level[i]);}return0;}