用“孩子链表表示法”表示二叉树并实现其操作,#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)设计函数实现如下功能:给定结点数据,判断其是否为叶子结点。如果是则输出叶子结点到根结点的路径
时间: 2024-01-29 17:05:03 浏览: 85
以下是完整的C语言代码,包含主函数和所有要求的功能:
```c
#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 InputTree(ChildTree *T);
int CountLeaf(ChildTree T);
int IsLeaf(ChildTree T, int i);
void PrintPathToRoot(ChildTree T, int i);
int main() {
ChildTree T;
InputTree(&T);
printf("叶子结点个数:%d\n", CountLeaf(T));
char data;
printf("输入一个节点数据:");
scanf("%c", &data);
getchar(); // 消耗掉输入缓冲区中的回车符
int i;
for (i = 0; i < T.TreeNodeNum; i++) {
if (T.Nodes[i].Data == data) {
if (IsLeaf(T, i)) {
printf("%c是叶子结点,路径为:", data);
PrintPathToRoot(T, i);
printf("\n");
}
else {
printf("%c不是叶子结点\n", data);
}
break;
}
}
if (i == T.TreeNodeNum) {
printf("找不到节点数据为%c的节点\n", data);
}
return 0;
}
// 输入二叉树
void InputTree(ChildTree *T) {
printf("输入二叉树节点数目:");
scanf("%d", &(T->TreeNodeNum));
getchar(); // 消耗掉输入缓冲区中的回车符
printf("输入各个节点的数据和孩子节点(输入格式为:节点数据 孩子节点数量 孩子节点1的位置 孩子节点2的位置 ...):\n");
int i, j, n;
char data;
ChildNode *p, *q;
for (i = 0; i < T->TreeNodeNum; i++) {
scanf("%c%d", &data, &n);
getchar(); // 消耗掉输入缓冲区中的空格符
T->Nodes[i].Data = data;
T->Nodes[i].FirstChild = NULL;
if (n > 0) {
T->Nodes[i].FirstChild = (ChildNode*)malloc(sizeof(ChildNode));
T->Nodes[i].FirstChild->Child = -1; // 初始化为一个不可能的值,以检查输入错误
T->Nodes[i].FirstChild->Next = NULL;
p = T->Nodes[i].FirstChild;
for (j = 0; j < n; j++) {
scanf("%d", &(p->Child));
if (p->Child < 0 || p->Child >= T->TreeNodeNum) {
printf("孩子节点位置输入错误!\n");
exit(1);
}
q = (ChildNode*)malloc(sizeof(ChildNode));
q->Child = -1; // 初始化为一个不可能的值,以检查输入错误
q->Next = NULL;
p->Next = q;
p = q;
}
}
getchar(); // 消耗掉输入缓冲区中的回车符
}
printf("输入树根节点的位置:");
scanf("%d", &(T->Root));
if (T->Root < 0 || T->Root >= T->TreeNodeNum) {
printf("树根节点位置输入错误!\n");
exit(1);
}
}
// 计算叶子结点个数
int CountLeaf(ChildTree T) {
int count = 0;
int i;
for (i = 0; i < T.TreeNodeNum; i++) {
if (T.Nodes[i].FirstChild == NULL) {
count++;
}
}
return count;
}
// 判断一个节点是否为叶子结点
int IsLeaf(ChildTree T, int i) {
return (T.Nodes[i].FirstChild == NULL);
}
// 输出一个叶子结点到根结点的路径
void PrintPathToRoot(ChildTree T, int i) {
if (i == T.Root) {
printf("%c", T.Nodes[i].Data);
}
else {
printf("%c-", T.Nodes[i].Data);
ChildNode *p = T.Nodes[T.Root].FirstChild;
while (p != NULL) {
if (p->Child == i) {
break;
}
p = p->Next;
}
if (p == NULL) {
printf("路径计算错误!\n");
exit(1);
}
PrintPathToRoot(T, T.Root);
}
}
```
这个程序通过 `InputTree` 函数输入二叉树,然后分别实现了 `CountLeaf` 函数计算叶子结点个数、`IsLeaf` 函数判断一个节点是否为叶子结点以及 `PrintPathToRoot` 函数输出一个叶子结点到根结点的路径。在 `main` 函数中,我们调用这些函数来完成题目要求的功能。
阅读全文