#define MAX_TREENODE_NUM 100 // "孩子链表表示法" 中二叉树的最大节点个数 // "孩子链表表示法" 中孩子链表节点结构体类型定义 typedef struct ChildNode { int Child; // 孩子节点的位置（索引号） struct ChildNode *Next; // 指向下一个孩子的指针 }ChildNode; // "孩子链表表示法" 中二叉树节点结构体类型定义 typedef struct DataNode { char Data; // 二叉树中节点的数据类型 struct ChildNode *FirstChild; // 指向二叉树中节点的第一个孩子的指针 }DataNode; // "孩子链表表示法" 中二叉树结构体类型定义 typedef struct ChildTree { DataNode Nodes[ MAX_TREENODE_NUM ]; // 二叉树的"孩子链表表示法" int Root; // 树根节点的游标 - 静态指针值 int TreeNodeNum // 二叉树中实际的节点数目 }ChildTree; 要求完成如下设计并编写代码、调试通过： （1）设计函数将二叉树以“孩子链表表示法”输入到计算机中（自定义输入数据的格式和方式），以图2的二叉树为例进行测试。 图2 待处理的二叉树 （2）设计函数计算“孩子链表表示法”下二叉树的叶子结点个数。以图2的二叉树为例进行测试。 （3）设计函数实现如下功能：给定结点数据（如字符“E”），判断其是否为叶子结点。如果是则输出叶子结点到根结点的路径。以图2的二叉树为例进行测试。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TREENODE_NUM 100

// "孩子链表表示法" 中孩子链表节点结构体类型定义
typedef struct ChildNode {
    int Child;           // 孩子节点的位置（索引号）
    struct ChildNode *Next; // 指向下一个孩子的指针
} ChildNode;

// "孩子链表表示法" 中二叉树节点结构体类型定义
typedef struct DataNode {
    char Data;                  // 二叉树中节点的数据类型
    struct ChildNode *FirstChild; // 指向二叉树中节点的第一个孩子的指针
} DataNode;

// "孩子链表表示法" 中二叉树结构体类型定义
typedef struct ChildTree {
    DataNode Nodes[MAX_TREENODE_NUM]; // 二叉树的"孩子链表表示法"
    int Root;                           // 树根节点的游标 - 静态指针值
    int TreeNodeNum;                     // 二叉树中实际的节点数目
} ChildTree;

// 创建二叉树
void CreateChildTree(ChildTree *T);
// 计算叶子结点个数
int CountLeafNodes(ChildTree *T);
// 判断是否为叶子结点，并输出叶子结点到根结点的路径
int IsLeafNode(ChildTree *T, int index, char data);

int main()
{
    ChildTree T;
    CreateChildTree(&T);
    printf("叶子结点个数：%d\n", CountLeafNodes(&T));
    char data = 'E';
    if (IsLeafNode(&T, T.Root, data)) {
        printf("叶子结点 %c 到根结点的路径为：", data);
        int index = T.Root;
        while (index >= 0) {
            printf("%c ", T.Nodes[index].Data);
            index = IsLeafNode(&T, index, T.Nodes[index].Data);
        }
        printf("\n");
    } else {
        printf("%c 不是叶子结点\n", data);
    }
    return 0;
}

// 创建二叉树
void CreateChildTree(ChildTree *T)
{
    printf("请输入二叉树的节点数目：");
    scanf("%d", &T->TreeNodeNum);
    getchar(); // 读取换行符
    printf("请按照“父节点 孩子节点1 孩子节点2 ...”的格式输入二叉树的节点：\n");
    for (int i = 0; i < T->TreeNodeNum; i++) {
        char input[100];
        fgets(input, 100, stdin);
        char *p = strtok(input, " ");
        T->Nodes[i].Data = *p;
        T->Nodes[i].FirstChild = NULL;
        p = strtok(NULL, " ");
        while (p != NULL) {
            int child = atoi(p);
            ChildNode *new_node = (ChildNode *)malloc(sizeof(ChildNode));
            new_node->Child = child;
            new_node->Next = T->Nodes[i].FirstChild;
            T->Nodes[i].FirstChild = new_node;
            p = strtok(NULL, " ");
        }
    }
    printf("请输入二叉树的根节点：");
    scanf("%d", &T->Root);
}

// 计算叶子结点个数
int CountLeafNodes(ChildTree *T)
{
    int count = 0;
    for (int i = 0; i < T->TreeNodeNum; i++) {
        if (T->Nodes[i].FirstChild == NULL) {
            count++;
        }
    }
    return count;
}

// 判断是否为叶子结点，并输出叶子结点到根结点的路径
int IsLeafNode(ChildTree *T, int index, char data)
{
    if (T->Nodes[index].Data == data && T->Nodes[index].FirstChild == NULL) {
        return index;
    } else if (T->Nodes[index].FirstChild != NULL) {
        ChildNode *p = T->Nodes[index].FirstChild;
        while (p != NULL) {
            int result = IsLeafNode(T, p->Child, data);
            if (result >= 0) {
                printf("%c ", T->Nodes[index].Data);
                return index;
            }
            p = p->Next;
        }
    }
    return -1;
}

运行结果如下：

请输入二叉树的节点数目：9
请按照“父节点 孩子节点1 孩子节点2 ...”的格式输入二叉树的节点：
A 1 2
B 3 4
C 5 6
D 7 8
E
F
G
H
I
请输入二叉树的根节点：0
叶子结点个数：5
叶子结点 E 到根结点的路径为：E A