03-树2 List Leaves
#include <stdio.h>#include <ctype.h>struct Node {int root; //记录节点是否是根节点int left;int right;};int main() {// freopen("test.txt", "r", stdin);int n;struct Node nodes[10];scanf("%d", &n);for (int i = 0; i < n; ++i) { //初始化树节点nodes[i].root = 1; //没连接的节点都是根节点nodes[i].left = -1; //没连接的节点左右儿子都为空nodes[i].right = -1;}for (int i = 0; i < n; ++i) { //构造树char ch1, ch2;scanf("\n%c %c", &ch1, &ch2);if (isdigit(ch1)) { //如果左儿子存在，将左儿子连接至该节点nodes[i].left = ch1 - '0'; //指针指向左儿子nodes[ch1 - '0'].root = 0; //左儿子取消根节点标记}if (isdigit(ch2)) {nodes[i].right = ch2 - '0';nodes[ch2 - '0'].root = 0;}}int root;for (int i = 0; i < n; ++i) //找到树根if (nodes[i].root == 1) {root = i;break;}//构造完树后，层序遍历树，依次输出叶节点；层序遍历过程：从根节点开始依次将左右儿子入队，直到队列为空int leaves = 0; //记录输出叶节点个数，方便输出时第一个节点输出前没有空格int queue[10]; //节点队列，只保存节点下标int head = 0, rear = 0;queue[rear++] = root; //根节点入队while (rear - head) {int node = queue[head++]; //队首节点出队if (nodes[node].left == -1 && nodes[node].right == -1) { //输出叶节点if (leaves)printf(" ");printf("%d", node);++leaves;}if (nodes[node].left != -1) { //如果存在，左儿子入队queue[rear++] = nodes[node].left;}if (nodes[node].right != -1) { //如果存在，右儿子入队queue[rear++] = nodes[node].right;}}return 0;}
题目：输出树的所有的叶节点
主要是层序遍历，用一个队列来顺序装左儿子，右儿子，head指向当前的遍历到的节点下标，rear指向将要遍历的最后的那个最右边的节点下标，如果head没有指向rear最后一个下标的话，就一直循环下去
秒速五厘米
亦凉
左手的ㄟ右手
还没有评论，来说两句吧...