PAT A1064

这道题自己起先想到的思路是根据完全二叉树性质，找出左右子树，递归进行；但是示例给出的思想很值得学习；对于一个二叉搜索树，其中序序列必递增的，所以可以利用这一点；我们先对输入的节点序列进行递增排序，之后我们对一个空的数组进行中序遍历，每遇到一个节点，就把相应的递增序列的值保存进去；这是一种对空序列进行中序序列建树的思想，很值得借鉴；#include<iostream>#include<vector>#include<stdlib.h>#include<stdio.h>#include<algorithm>using namespace std;using std::vector;int n;const int maxn=1010;int number[maxn];int CBT[maxn];int index=0;void inorder(int root){ if(root>n) return; inorder(2root); CBT[root]=number[index++]; inorder(2root+1);}int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&number[i]); } sort(number,number+n); inorder(1); for(int i=1;i<=n;i++){ printf("%d",CBT[i]); if(i<n) printf(" “); } system(“pause”); return 0;}