1048.二叉树的遍历

Description

给出一棵完美二叉树（所有叶子节点高度相同，所有非叶子节点都有两个子节点）的描述，输出按层次顺序遍历这棵二叉树的结果。二叉树的每个节点都对应于一个正整数作为标记。对于一棵有n个节点的二叉树，其节点标记的取值范围为1至n，且任意两个节点标记不相等。

Input Format

第1行：1个正整数n，表示二叉树的节点个数为n；第2行至输入结束：每行有3个正整数a、b和c，设分别为节点A、B和C的标记，表示A的左儿子节点是B，右儿子节点是C。

Output Format

输出共n行，每行一个正整数，为遍历结果中相应次序的节点的标记。

Sample Input

7
3 2 1
1 7 6
2 4 5

Sample Output

3
2
1
4
5
7
6

Limits

对于30%的数据，3 <= n <= 127；对于100%的数据，3 <= n <= 1023。所有输入数据保证有效。
时间限制：1000ms，内存限制：30000kb。

Hint

先根据输入数据找到该二叉树的根，然后从根开始逐层遍历该二叉树。

代码

#include<iostream>
#include<queue>
using namespace std;
#define Maxn 1024

typedef struct{
    int parentData;
    int lchild;
    int rchild;
} Node;


int main()
{
    int flag[Maxn] ={0};// 用于判定是否为根结点
    int n;//结点个数
    cin>>n;
    Node TNode  [Maxn];
    for(int i=0;i<n/2;i++)
    {
         int parent;
         cin>>parent;
         TNode[parent].parentData = parent;
         cin>>TNode[parent].lchild;
         cin>>TNode[parent].rchild;
         flag[TNode[parent].lchild] = 1;// 根结点不可能为儿子
         flag[TNode[parent].rchild] = 1;
    }

    //寻找根结点
    int root;
    for(int i=1;i<n;i++)
    {
        if(flag[i]==0)
            root = i;
    }

    //从根结点开始遍历，利用队列
    queue  <int> s;
     s.push(root);
     int i =1;
     while(i<=n)
     {
         i++;
         int tmp;
         tmp = s.front();
         cout<<  tmp<<endl;
         s.pop();
         int index1 = TNode[tmp].lchild;
         int index2 = TNode[tmp].rchild;
         s.push(index1);
         s.push(index2);
     }
     return 0;
}