用“孩子链表表示法”表示二叉树并实现其操作,#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）设计函数计算“孩子链表表示法”下二叉树的叶子结点个数。 （3）设计函数实现如下功能：给定结点数据（如字符“E”），判断其是否为叶子结点。如果是则输出叶子结点到根结点的路径。

1. 输入二叉树以“孩子链表表示法”到计算机中

void InputChildTree(ChildTree* tree) {
    printf("请输入二叉树的节点数目：");
    scanf("%d", &tree->TreeNodeNum);
    printf("请输入二叉树的节点数据：");
    for (int i = 0; i < tree->TreeNodeNum; ++i) {
        scanf("%s", &tree->Nodes[i].Data);
        tree->Nodes[i].FirstChild = NULL; // 初始化每个节点的孩子链表为空
    }
    printf("请输入二叉树的根节点位置（从0开始）：");
    scanf("%d", &tree->Root);
    printf("请输入每个节点的孩子节点（以-1结束）：");
    int parent, child;
    for (int i = 0; i < tree->TreeNodeNum; ++i) {
        parent = i;
        scanf("%d", &child);
        while (child != -1) {
            AddChild(tree, parent, child);
            scanf("%d", &child);
        }
    }
}

void AddChild(ChildTree* tree, int parent, int child) {
    ChildNode* p = (ChildNode*)malloc(sizeof(ChildNode));
    p->Child = child;
    p->Next = NULL;
    if (tree->Nodes[parent].FirstChild == NULL) {
        tree->Nodes[parent].FirstChild = p;
    } else {
        ChildNode* q = tree->Nodes[parent].FirstChild;
        while (q->Next != NULL) {
            q = q->Next;
        }
        q->Next = p;
    }
}

2. 计算“孩子链表表示法”下二叉树的叶子结点个数

int CountLeafNodes(ChildTree* tree) {
    int count = 0;
    for (int i = 0; i < tree->TreeNodeNum; ++i) {
        if (tree->Nodes[i].FirstChild == NULL) {
            ++count;
        }
    }
    return count;
}

3. 给定结点数据，判断是否为叶子结点，并输出叶子结点到根结点的路径

void FindPath(ChildTree* tree, char data) {
    int* path = (int*)malloc(sizeof(int) * tree->TreeNodeNum);
    int pathLen = 0;
    int nodeIndex = FindNode(tree, tree->Root, data);
    if (nodeIndex != -1) {
        FindPathHelper(tree, nodeIndex, path, &pathLen);
        printf("节点%c的路径：", data);
        for (int i = pathLen - 1; i >= 0; --i) {
            printf("%c ", tree->Nodes[path[i]].Data);
        }
        printf("\n");
    } else {
        printf("未找到节点%c\n", data);
    }
    free(path);
}

int FindNode(ChildTree* tree, int nodeIndex, char data) {
    if (nodeIndex == -1) {
        return -1;
    }
    if (tree->Nodes[nodeIndex].Data == data) {
        return nodeIndex;
    }
    ChildNode* p = tree->Nodes[nodeIndex].FirstChild;
    while (p != NULL) {
        int result = FindNode(tree, p->Child, data);
        if (result != -1) {
            return result;
        }
        p = p->Next;
    }
    return -1;
}

void FindPathHelper(ChildTree* tree, int nodeIndex, int* path, int* pathLen) {
    path[(*pathLen)++] = nodeIndex;
    if (tree->Nodes[nodeIndex].FirstChild == NULL) {
        return;
    }
    ChildNode* p = tree->Nodes[nodeIndex].FirstChild;
    while (p != NULL) {
        FindPathHelper(tree, p->Child, path, pathLen);
        p = p->Next;
    }
}