PAT-A1102

#include<stdio.h> #include<queue> using namespace std; int n, sum=0; bool have_root[15]={false}; struct pnode{ int left, right; }node[15]; int check(char a){ if(a=='-')return -1; else {have_root[a-'0']=true;return a-'0';} } void postorder(int root){//先序或后序其实都可以 if(root==-1)return; int temp=node[root].left;node[root].left=node[root].right;node[root].right=temp;//Swap postorder(node[root].left); postorder(node[root].right); } void levelorder(int root){ if(root==-1)return; queue<int>que; que.push(root); while(!que.empty()){ int k=que.front(); que.pop(); printf("%d",k);sum++; if(sum<n)printf(" "); else printf("\n"); if(node[k].left!=-1)que.push(node[k].left); if(node[k].right!=-1)que.push(node[k].right); } } void inorder(int root){ if(root==-1)return; inorder(node[root].left); printf("%d",root);sum++; if(sum<n)printf(" "); else printf("\n"); inorder(node[root].right); } int main(){ int i, root; char c1, c2; scanf("%d",&n); for(i=0;i<n;i++){ getchar(); scanf("%c %c",&c1,&c2); node[i].left=check(c1); node[i].right=check(c2); } for(i=0;i<n;i++){//找根节点 if(!have_root[i]){root=i;break;}} //开始反转 postorder(root); //输出 levelorder(root); sum=0; inorder(root); return 0; }