PAT - 03-树2 List Leaves (25分)

03-树2 List Leaves   (25分)

Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer $N$ ($\le 10$) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to $N-1$. Then $N$ lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a "-" will be put at the position. Any pair of children are separated by a space.

Output Specification:

For each test case, print in one line all the leaves' indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

Sample Input:

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

Sample Output:

4 1 5

思路分析：建立一棵树，每行代表一个结点，序号从0~N（N < 9 ），‘ - ’ 代表没有孩子。首先找到树的根，然后依次从根开始查找当前结点的左孩子和右孩子，并加入到队列中，每次循环队列出队一个结点，如果该结点都没有左右孩子，则输出。（BFS，即层序遍历的思想）。可以不用建立一棵树，直接用数组模拟，这样更方便一些。

#include <cstdio>
#include <cstdlib>
#include <queue>

#define MAX 10

using namespace std;

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

Node node[MAX];
int isRoot[MAX] = { 0 };

int main() {
    //freopen( "123.txt", "r", stdin );
    int n;
    scanf( "%d", &n );
    char ch = getchar();
    for( int i = 0; i < n; i++ ) {
        char left, right;
        scanf( "%c %c", &left, &right );
        char ch = getchar();
        node[i].index = i;
        if( left != '-' ) {
            node[i].lchild = left - '0';
        }
        else {
            node[i].lchild = -1;
        }
        if( right != '-' ) {
            node[i].rchild = right - '0';
        }
        else {
            node[i].rchild = -1;
        }
    }

    //输出每个结点信息
    //for( int i = 0; i < n; i++ ) {
    //    printf( "%d %d\n", node[i].lchild, node[i].rchild );
    //}
    
    // 查找根节点
    for( int i = 0; i < n; i++ ) {
        int child;
        if( node[i].lchild != -1 ) {
            child = node[i].lchild;
            isRoot[child] = 1;
        }
        if( node[i].rchild != -1 ) {
            child = node[i].rchild;
            isRoot[child] = 1;
        }
    }

    //for( int i = 0; i < n; i++ ) {
    //    printf( "%d ", isRoot[i] );
    //}
    //printf( "\n" );
    
    // 查找树根
    int root = 0;
    for( int i = 0; i < n; i++ ) {
        if( isRoot[i] == 0 ) {
            root = i;
            break;
        }
    }

    //printf( "root: %d\n", root );
    // 层序遍历
    queue<Node> q;
    q.push( node[root] );

    int count = 0;
    while( !q.empty() ) {
        Node curNode = q.front();
        q.pop();
        if( curNode.lchild != -1 ) {
            int child = curNode.lchild;
            q.push( node[child] );
        }
        if( curNode.rchild != -1 ) {
            int child = curNode.rchild;
            q.push( node[child] );
        }
        if( curNode.lchild == -1 && curNode.rchild == -1 ) {
            if( count == 0 ) {
                printf( "%d", curNode.index );
                count = 1;
            }
            else {
                printf( " %d", curNode.index );
            }
        }
    }
    return 0;
}