PAT甲级1102.

目录

A1102

题目

样例

输入:

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

输出:

3 7 2 6 4 0 5 1
6 5 7 4 3 2 0 1

思路和坑点

　　对树进行左右翻转，然后进行层序和中序的遍历。在读入孩子的时候按照先右后左的顺序读入。层序遍历使用队列实现，中序遍历使用递归方法实现，注意控制输出序列的空格。
　　坑点：
　　根未知，所以要根据树的结构筛选出根来，即没有被指向的结点（也就是没有父节点的）便是根。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{                            //输的节点定义，使用二位数组存放数，左右孩子用下标序号表示 
    int l,r;
    node():l(-1),r(-1){}                        //默认构造函数，初始化左右孩子为-1表示空 
    node(int _l,int _r):l(_l),r(_r){}           //带参数的构造函数 
}Node;
vector<Node> T;                                 //用于存放树 
int inocnt=0;                                   //中序遍历控制空格的计数器 
map<int,bool> mp;                               //记录是不是根，如果不是就从中删掉 
void levelorder(int root);                      //层序遍历 
void inorder(int root);                         //中序遍历 
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    scanf("%d",&n);                             //读入数据个数 
    for(int i=0;i<n;i++){
        mp[i]=true;                             //初始化根的标记，假定所有的都是根 
    }
    for(int i=0;i<n;i++){                       //依次读入0-N-1的所有结点的孩子状况 
        string left,right;                      //由于存在-  这样的情况表示没有孩子，因此使用字符串读入（字符读入要考虑空格干扰） 
        Node temp;                              //创建一个临时的结点 
        cin>>right>>left;                       //结果要求翻转的树，因此按照先右后左的顺序读入 
        if(right!="-"){                         //如果右孩子不是空 
            int num;
            sscanf(right.c_str(),"%d",&num);    //将其转化为数字记录进孩子 
            mp.erase(num);                      //同时剔除该顶点不是根 
            temp.r=num;
        }
        if(left!="-"){                          //同理处理左孩子 
            int num;
            sscanf(left.c_str(),"%d",&num);
            mp.erase(num);
            temp.l=num;
        }
        T.push_back(temp);                      //然后将其存入数组（如果两个孩子都没有，因为有默认初始化为-1，因此不用特殊处理） 
    }
    int root=mp.begin()->first;                 //剩下的唯一一个标记就是根了 
    levelorder(root);                           //层序遍历 
    putchar('\n');                             
    inorder(root);                              //中序遍历 
    
    return 0;    
}
void levelorder(int root)                       //使用队列实现层序遍历 
{
    int cnt=0;                                  //计数器，用于控制空格 
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        int now=q.front();
        if(cnt) putchar(' ');
        printf("%d",now);
        cnt++;
        q.pop();
        if(T[now].l!=-1)    q.push(T[now].l);
        if(T[now].r!=-1)    q.push(T[now].r);
    }
}
void inorder(int root)                          //递归实现的中序遍历 
{
    if(root==-1) return ;
    inorder(T[root].l);
    if(inocnt) putchar(' ');                    //如果不是第一个输出，需要前置空格 
    printf("%d",root);
    inocnt++;
    inorder(T[root].r);
}