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

Solution题目要求给一串构成树的序列已知该树是完全二叉搜索树求它的层序遍历的序列。总得概括来说已知中序可求root下标可以求出层序。1因为二叉搜索树的中序满足是一组序列的从小到大排列所以只需排序所给序列即可得到中序。2因为根据完全二叉树的结点数可以求出它的根结点在中序中对应的下标要知道根结点在中序中的下标只要知道左子节点的个数即可。3已知了中序又可以根据结点数求出根结点的下标就可以递归求出左右子树的根结点的下标。4结点的左孩子为2 * i 1右孩子2 * i 2就可以根据结点下标和中序数组赋值level数组。5最后输出所有结点的层序数组level。画张图说明吧代码如下#includeiostream#includemath.h#includevector#includealgorithmusing namespace std;vectorintlevel,in;//level为层序in为中序voidlevel_order(intleft,intright,intindex){if(leftright){return;}intnright-left1;intllog(n1)/log(2);// 除了最后一层的层数intleaven-(pow(2,l)-1);//最后一层的叶子节点数introotleft(pow(2,l-1)-1)min((int)pow(2,l-1),leave);// pow(2,l-1)-1是除了root结点所在层和最后一层外//左子树的结点个数pow(2,l-1)是l1层最多拥有的属于根结点左子树的结点个数//min(pow(2,l-1),leave)是最后一个结点真正拥有的属于根结点左子树上的结点个数level[index]in[root];level_order(left,root-1,2*index1);level_order(root1,right,2*index2);}intmain(){intn;cinn;in.resize(n);level.resize(n);intnum;for(inti0;in;i){cinin[i];}sort(in.begin(),in.end());level_order(0,n-1,0);coutlevel[0];for(inti1;in;i){cout level[i];}return0;}更简单的解法1如果使用数组来存放完全二叉树那么对完全二叉树当中的任何一个结点设编号为x其中根结点编号为1其左孩子结点的编号一定时2x而右孩子结点的编号一定时2x1,。那么就可以开一个数组level[maxn]其中level[1]~level[n]按层序存放完全二叉树的n个结点这个数组就存放了一棵完全二叉树。2考虑到对一棵二叉排序树来说其中序遍历序列是递增的先将输入的数字从小到大排序然后对level数组表示的二叉树进行中序排序并在遍历的过程中将数字从小到大填入数组。代码如下#includeiostream#includealgorithm#includestdio.h#includecmath#includequeue#includecstring#includevector#includestack#includemap#defineMAX 1005#defineINF 0x3f3f3f3ftypedeflonglongll;usingnamespacestd;intn,id0;intin[MAX],level[MAX];voidinorder(introot){//中序遍历if(rootn)return;inorder(root*2);//往左子树递归level[root]in[id];//根结点处赋值in[id]inorder(root*21);//往右子树递归}intmain(){scanf(%d,n);for(inti0;in;i){scanf(%d,in[i]);}sort(in,inn);inorder(1);for(inti1;in;i){printf(%s%d,i1?: ,level[i]);}return0;}