C语言设计函数计算“孩子链表表示法”下二叉树的叶子结点个数。#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;

下面是计算"孩子链表表示法"下二叉树叶子结点个数的C语言函数实现：

// 计算二叉树中叶子结点的个数
int CountLeafNodes(ChildTree *T)
{
    int LeafNodeCount = 0;
    int i;
    ChildNode *p;

    // 遍历整个二叉树
    for (i = 0; i < T->TreeNodeNum; i++)
    {
        // 如果节点没有孩子，即为叶子结点
        if (T->Nodes[i].FirstChild == NULL)
        {
            LeafNodeCount++; // 叶子结点个数加1
        }
        else // 如果有孩子，遍历其孩子链表
        {
            p = T->Nodes[i].FirstChild;
            while (p != NULL)
            {
                p = p->Next;
            }
        }
    }

    return LeafNodeCount;
}

该函数首先初始化叶子结点个数为0，然后遍历整个二叉树，对于每个节点，如果它没有孩子，则它是一个叶子结点，叶子结点个数加1；否则，遍历它的孩子链表。最终返回叶子结点个数。

相关问题

C语言计算“孩子链表表示法”下二叉树的叶子结点个数#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;

下面是计算孩子链表表示法下二叉树的叶子结点个数的 C 语言代码：

int CountLeafNodes(ChildTree* tree, int nodeIndex)
{
    if (nodeIndex == -1) { // 空节点，返回 0
        return 0;
    }
    if (tree->Nodes[nodeIndex].FirstChild == NULL) { // 叶子节点，返回 1
        return 1;
    }
    int leftChild = tree->Nodes[nodeIndex].FirstChild->Child;
    int rightChild = -1;
    if (tree->Nodes[nodeIndex].FirstChild->Next != NULL) {
        rightChild = tree->Nodes[nodeIndex].FirstChild->Next->Child;
    }
    return CountLeafNodes(tree, leftChild) + CountLeafNodes(tree, rightChild);
}

该算法使用递归的方式遍历二叉树，如果当前节点为空，返回 0；如果当前节点为叶子节点，返回 1；否则，递归遍历左右子树，并将结果相加。其中，左子树的根节点为当前节点的第一个孩子，右子树的根节点为当前节点的第二个孩子（如果存在）。注意，当右子树为空时，右子树的根节点索引值为 -1。最后，调用该函数时，传入的参数 nodeIndex 应为根节点的索引值。

用“孩子链表表示法”表示二叉树并实现其操作，#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; 要求完成如下设计并编写完整的c语言代码（包含主函数）、调试通过： （1）设计函数将二叉树以“孩子链表表示法”输入到计算机中（自定义输入数据的格式和方式）设计函数计算“孩子链表表示法”下二叉树的叶子结点个数。 （3）设计函数实现如下功能：给定结点数据，判断其是否为叶子结点。如果是则输出叶子结点到根结点的路径

代码如下：

#include <stdio.h>
#include <stdlib.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);
void PrintChildTree(ChildTree T);
int CountLeafNodes(ChildTree T);
int IsLeafNode(ChildTree T, int i);
void PrintPathFromNodeToRoot(ChildTree T, int i);

int main() {
    ChildTree T;
    CreateChildTree(&T);
    printf("孩子链表表示法下二叉树的叶子结点个数为：%d\n", CountLeafNodes(T));
    char c;
    printf("请输入要查找的结点：");
    scanf(" %c", &c);
    int i;
    for (i = 0; i < T.TreeNodeNum; i++) {
        if (T.Nodes[i].Data == c) {
            break;
        }
    }
    if (i == T.TreeNodeNum) {
        printf("未找到该节点\n");
        return 0;
    }
    if (IsLeafNode(T, i)) {
        printf("%c 是叶子结点\n", c);
    } else {
        printf("%c 不是叶子结点\n", c);
        printf("从叶子结点 %c 到根结点的路径为：", T.Nodes[i].Data);
        PrintPathFromNodeToRoot(T, i);
        printf("\n");
    }
    return 0;
}

void CreateChildTree(ChildTree *T) {
    printf("请输入二叉树中结点的个数：");
    scanf("%d", &T->TreeNodeNum);
    printf("请按照层序遍历的顺序依次输入每个结点的数据（空格分隔），如果该节点没有孩子则输入“#”：\n");
    for (int i = 0; i < T->TreeNodeNum; i++) {
        // 读入结点数据
        scanf(" %c", &T->Nodes[i].Data);
        // 初始化孩子链表为空
        T->Nodes[i].FirstChild = NULL;
        // 判断是否为根结点
        if (i == 0) {
            T->Root = i;
        } else {
            // 读入该节点的父节点位置
            int parent;
            scanf("%d", &parent);
            // 将该节点添加到父节点的孩子链表中
            ChildNode *p = T->Nodes[parent].FirstChild;
            if (p == NULL) {
                T->Nodes[parent].FirstChild = (ChildNode *) malloc(sizeof(ChildNode));
                T->Nodes[parent].FirstChild->Child = i;
                T->Nodes[parent].FirstChild->Next = NULL;
            } else {
                while (p->Next != NULL) {
                    p = p->Next;
                }
                p->Next = (ChildNode *) malloc(sizeof(ChildNode));
                p->Next->Child = i;
                p->Next->Next = NULL;
            }
        }
    }
}

void PrintChildTree(ChildTree T) {
    printf("孩子链表表示法下的二叉树：\n");
    for (int i = 0; i < T.TreeNodeNum; i++) {
        printf("%c -> ", T.Nodes[i].Data);
        ChildNode *p = T.Nodes[i].FirstChild;
        while (p != NULL) {
            printf("%c ", T.Nodes[p->Child].Data);
            p = p->Next;
        }
        printf("\n");
    }
}

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 i) {
    return T.Nodes[i].FirstChild == NULL;
}

void PrintPathFromNodeToRoot(ChildTree T, int i) {
    printf("%c", T.Nodes[i].Data);
    while (i != T.Root) {
        // 找到父节点位置
        int parent = -1;
        for (int j = 0; j < T.TreeNodeNum; j++) {
            ChildNode *p = T.Nodes[j].FirstChild;
            while (p != NULL) {
                if (p->Child == i) {
                    parent = j;
                    break;
                }
                p = p->Next;
            }
            if (parent != -1) {
                break;
            }
        }
        // 输出父节点数据并更新 i 值
        printf(" <- %c", T.Nodes[parent].Data);
        i = parent;
    }
}