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<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm> 
#include<map>
#include<unordered_map>
#include<vector>
#include<queue> 
#include<stack>
#include<string>
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);
}