03-树2 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:

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

Sample Output:

4 1 5

结构 TreeNode数组

1. 结点值Element
2. 左子树
3. 右子树
4. 结点数组T1用于存放输入的数据，T2存放层序遍历的数据

生成二叉树 CreateBiTree

1. 输入结点数
2. check数组用来判断根的位置,check[i]初始化为0
3. 读取N个结点的左、右孩子
4. 如果读取的非‘-’数据则写入左子树,同时check标记该点有子树，读空则为Null
5. 如果读取非’-‘数据则写入右子树，同时check标记该点有子树，读入空则为Null
6. 写入结点的值i
7. 如果左右都为’-‘，叶子数leves加1
8. 遍历标记数组，index的值check为0，则说明该点无父结点，是根结点

主要步骤

1. 创建二叉树，返回根结点及叶子数
2. 将根结点添加到T2数组的第1个位置
3. 遍历数组，直到头、尾指针相同
4. 取出队列头结点FirstCell
5. 如果左、右子树都为空，则打针叶子结点
6. 如果头结点FirstCell的左子树不空，加入左子树到队列中
7. 如果头结点FirstCell的右子树不空，加入右子树到队列中

编码

#include <stdio.h>
#define MaxTree 10
#define ElementType int
#define Tree int
#define Null -1

typedef struct TreeNode PtrToTNode;
struct TreeNode {
    // 1.结点值
    ElementType Element;
    // 2.左子树
    Tree Left;
    // 3.右子树
    Tree Right;
} T1[MaxTree], T2[MaxTree];
// 4.结点数组T1用于存放输入的数据，T2存放层序遍历的数据

Tree CreateBiTree(struct TreeNode T[], int *leaves);

int main() {
    Tree R1;
    int Front, Rear, LeavesNub;
    PtrToTNode FirstCell;
    // 1.创建二叉树，返回根结点及叶子数
    R1 = CreateBiTree(T1, &LeavesNub);
    Front = Rear = 0;
    // 2.将根结点添加到T2数组的第1个位置
    T2[Rear++] = T1[R1];
    // 3.遍历数组，直到头、尾指针相同
    while (Rear != Front) {
        // 4.取出队列头结点FirstCell
        FirstCell = T2[Front++];
        // 5.如果左、右子树都为空，则打针叶子结点
        if (FirstCell.Right == Null && FirstCell.Left == Null) {
            if (LeavesNub != 1)
                printf("%d ", FirstCell.Element);
            else
                printf("%d", FirstCell.Element);
            LeavesNub--;
        }
        // 6.如果头结点FirstCell的左子树不空，加入左子树到队列中
        if (FirstCell.Left != Null) {
            T2[Rear++] = T1[FirstCell.Left];
        }
        // 7.如果头结点FirstCell的右子树不空，加入右子树到队列中
        if (FirstCell.Right != Null) {
            T2[Rear++] = T1[FirstCell.Right];
        }
    }

    return 0;
}

/**
 * 从输入的数据中生成二叉树，保存在结构体数组中
 * @param T  元素{index left right}
 * @param leaves 统计叶子总数，用于控制输出格式
 * @return
 */
Tree CreateBiTree(struct TreeNode T[], int *leaves) {
    int i, N, check[MaxTree];
    Tree Root = Null;
    char cl, cr;
    // 1.输入结点数
    scanf("%d\n", &N);
    if (N) {
        //2.check数组用来判断根的位置,check[i]初始化为0
        for (i = 0; i < N; i++)
            check[i] = 0;
        *leaves = 0;
        // 3.读取N个结点的左、右孩子
        for (i = 0; i < N; i++) {
            scanf("%c %c\n", &cl, &cr);
            // 4.如果读取的非‘-’数据则写入左子树,同时check标记该点有子树，读空则为Null
            if (cl != '-') {
                T[i].Left = cl - '0';
                check[T[i].Left] = 1;
            } else
                T[i].Left = Null;
            // 5.如果读取非'-'数据则写入右子树，同时check标记该点有子树，读入空则为Null
            if (cr != '-') {
                T[i].Right = cr - '0';
                check[T[i].Right] = 1;
            } else
                T[i].Right = Null;
            // 6.写入结点的值
            T[i].Element = i;
            // 7.如果左右都为'-'，叶子数leves加1
            if (cl == '-' && cr == '-') {
                (*leaves)++;
            }
        }
        //8.遍历标记数组，index的值check为0，则说明该点无父结点，是根结点
        for (i = 0; i < N; i++) {
            if (!check[i]) {
                Root = i;
                break;
            }
        }
    }
    return Root;
}

小结：

1. 数据结构选择，采用结构体数组2个，一个用于存储输入数据，一个用于层序遍历输出
2. 层序遍历需要使用队列，则需要头、尾指针(Front,Rear)
3. 为满足输出格式，加入叶子结点数指针变量LeavesNub