用C语言设计函数将二叉树以“孩子链表表示法”输入到计算机中和二叉树的叶子结点个数并且给定结点数据(如字符“E”),判断其是否为叶子结点。如果是则输出叶子结点到根结点的路径。并给出主函数示例#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;
时间: 2023-12-14 18:38:56 浏览: 131
用C语言求二叉树叶子结点
4星 · 用户满意度95%
下面是输入二叉树以孩子链表表示法的函数实现:
```c
void InputTree(ChildTree *T){
int i, j, k;
char ch;
ChildNode *p, *q;
T->TreeNodeNum = 0; // 初始化节点数为0
printf("请输入根节点的数据:");
scanf(" %c", &ch); // 输入根节点数据
T->Nodes[0].Data = ch; // 根节点存储在0号位置
T->Nodes[0].FirstChild = NULL; // 根节点没有孩子
T->Root = 0; // 根节点位置为0
T->TreeNodeNum++; // 节点数加1
printf("请按照从根节点到叶子节点的顺序输入二叉树的数据,输入#表示空节点:\n");
for(i = 0; i < MAX_TREENODE_NUM; i++){
printf("请输入第%d个节点的左孩子的位置:", i + 1);
scanf("%d", &j); // 输入左孩子的位置
if(j == -1){ // 输入-1表示该节点没有左孩子
T->Nodes[i].FirstChild = NULL;
}
else{
p = (ChildNode*)malloc(sizeof(ChildNode)); // 新建一个孩子链表节点
p->Child = j; // 存储孩子位置
p->Next = NULL; // 新建的节点没有下一个孩子
T->Nodes[i].FirstChild = p; // 将该孩子节点作为该节点的第一个孩子
}
printf("请输入第%d个节点的右孩子的位置:", i + 1);
scanf("%d", &k); // 输入右孩子的位置
if(k == -1){ // 输入-1表示该节点没有右孩子
continue;
}
else{
q = (ChildNode*)malloc(sizeof(ChildNode)); // 新建一个孩子链表节点
q->Child = k; // 存储孩子位置
q->Next = NULL; // 新建的节点没有下一个孩子
if(T->Nodes[i].FirstChild){ // 如果该节点已经有孩子
p->Next = q; // 将该孩子节点接在该节点的孩子链表末尾
}
else{ // 如果该节点还没有孩子
T->Nodes[i].FirstChild = q; // 将该孩子节点作为该节点的第一个孩子
}
}
T->TreeNodeNum++; // 节点数加1
printf("是否继续输入?(y/n)");
scanf(" %c", &ch);
if(ch == 'n' || ch == 'N'){
break;
}
}
}
```
下面是计算二叉树叶子节点数的函数实现:
```c
int CountLeaf(DataNode node){
if(node.FirstChild == NULL){ // 如果该节点没有孩子,即为叶子节点
return 1;
}
else{ // 如果该节点有孩子,则递归计算其所有孩子的叶子节点数目之和
ChildNode *p = node.FirstChild;
int sum = 0;
while(p){ // 遍历孩子链表
sum += CountLeaf(*(p++)); // 计算孩子节点的叶子节点数目之和
}
return sum;
}
}
```
下面是判断给定节点是否为叶子节点并输出叶子节点到根节点的路径的函数实现:
```c
void FindNodePath(DataNode node, char target, char path[], int len){
if(node.Data == target){ // 如果找到了目标节点
printf("叶子节点到根节点的路径为:");
for(int i = len - 1; i >= 0; i--){ // 从后往前输出路径
printf("%c ", path[i]);
}
printf("\n");
}
else if(node.FirstChild == NULL){ // 如果该节点为叶子节点但不是目标节点
return; // 返回上一级节点
}
else{ // 如果该节点不是叶子节点
ChildNode *p = node.FirstChild;
while(p){ // 遍历孩子链表
path[len] = node.Data; // 将该节点的数据加入路径
FindNodePath(T->Nodes[p->Child], target, path, len + 1); // 递归查找孩子节点
p = p->Next; // 查找下一个孩子节点
}
}
}
```
下面是主函数的示例:
```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(DataNode node);
void FindNodePath(DataNode node, char target, char path[], int len);
int main(){
ChildTree T;
InputTree(&T);
printf("二叉树中叶子节点的个数为:%d\n", CountLeaf(T.Nodes[T.Root]));
char target;
printf("请输入要查找的节点数据:");
scanf(" %c", &target);
char path[MAX_TREENODE_NUM];
FindNodePath(T.Nodes[T.Root], target, path, 0);
return 0;
}
```
阅读全文