03-树2 List Leaves

03-树2 List Leaves

来自：PTA_数据结构_List Leaves

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 (≤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:

Sample Output:

4 1 5

程序代码：

#include <stdio.h>
#define MaxTree 10
#define Null -1     //将Null定义为-1而不能是0，因为数组下标为0的地方仍保存有节点
typedef char ElementType;
typedef int Tree;
struct TreeNode{    //定义二叉树节点
    Tree Left;
    Tree Right;
}T[MaxTree];   //c语言结构体的相关知识。
int N,check[MaxTree];   //check数组用于寻找树的根节点

Tree BuildTree(struct TreeNode T[]){
    int Root=Null,i;    //刚开始将节点置为空，若为空树的时候可返回Null
    char cl,cr;
    scanf("%d",&N); 
    if(N){              //如果不为空树的话
        for(i=0;i<N;i++) check[i]=0;    //将check数组置为0
        for(i=0;i<N;i++){
            scanf("\n%c %c",&cl,&cr); //把换行符放在前面吃掉前面scanf后的回车，而最后一个scanf不能有回车，一举两得
            if(cl!='-'){                            //在输入语句中的换行符有用吗？？有用，在涉及到字符输入的时候有用，换行本身就是一种字符。
                T[i].Left=cl-'0';
                check[T[i].Left]=1;
            }
            else                    
                T[i].Left=Null; 
								//要判断节点的左右子树是否存在,不存在也要设置为Null,因为在判断树的同构时会要用到。
            if(cr!='-'){
                T[i].Right=cr-'0';
                check[T[i].Right]=1;
            }
            else 
                T[i].Right=Null;

        }
        for(i=0;i<N;i++)
            if(!check[i])   break;
        Root=i;
    }
    return Root; 
}


int main(){
    Tree R;     
    R=BuildTree(T);
    int quene[MaxTree];
    for (int i = 0; i < MaxTree; i++)
    {
        quene[i] = -1;
    }
    
    quene[0] = R;
    int temp = 0;
    for (int i = 0; i < N; i++)
    {
        if (T[quene[i]].Left!=Null)
        {
            quene[++temp] = T[quene[i]].Left;
        }
        if (T[quene[i]].Right!=Null)
        {
            quene[++temp] = T[quene[i]].Right;
        }       
    }

    int flag = 0;
    for (int i = 0; quene[i]>-1; i++)
    {
        if ((T[quene[i]].Right==Null)&(T[quene[i]].Left==Null))
        {
            if (flag)       //放置空格的技巧。（数字之间空格分开，最后一个数字后无空格）
            {
                printf(" ");
            }else
            {
                flag = 1;
            } 
            printf("%d", quene[i]);
        }
        
    }

    return 0;
}