PAT A1099

和完全二叉排序树那道题类似，采用的方法还是中序遍历空树填节点的方法；代码如下：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<algorithm>#include<queue>using namespace std;using std::vector;using std::queue;const int maxn=110;struct node{ int data=-1; int lchild=-1; int rchild=-1;}Node[maxn];int n;vector<int>input;vector<int>output;int index=0;void inorder(int root){ if(root==-1) return; inorder(Node[root].lchild); Node[root].data=input[index++]; inorder(Node[root].rchild);}void layer(int root){ queue<int>q; q.push(root); while(!q.empty()){ int x=q.front(); q.pop(); output.push_back(Node[x].data); if(Node[x].lchild!=-1){ q.push(Node[x].lchild); } if(Node[x].rchild!=-1){ q.push(Node[x].rchild); } }}int main(){ int a,b; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d%d",&a,&b); Node[i].lchild=a; Node[i].rchild=b; } for(int i=0;i<n;i++){ scanf("%d",&a); input.push_back(a); } sort(input.begin(),input.end()); inorder(0); layer(0); for(int i=0;i<n;i++){ if(i==0) printf("%d",output[i]); else printf(" %d",output[i]); } system(“pause”); return 0;}