C语言二叉树将二叉树以“孩子链表表示法”输入到计算机中,计算“孩子链表表示法”下二叉树的叶子结点个数。给定结点数据(如字符“E”),判断其是否为叶子结点。如果是则输出叶子结点到根结点的路径。
时间: 2023-12-25 08:05:43 浏览: 69
用C语言求二叉树叶子结点
4星 · 用户满意度95%
以下是 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
typedef struct node {
char data; // 结点数据
struct node *lchild; // 左孩子指针
struct node *rchild; // 右孩子指针
} Node, *BiTree;
// 创建二叉树
void createBiTree(BiTree *root) {
char ch;
scanf("%c", &ch);
if (ch == '#') {
*root = NULL;
} else {
*root = (Node *)malloc(sizeof(Node));
(*root)->data = ch;
createBiTree(&((*root)->lchild));
createBiTree(&((*root)->rchild));
}
}
// 计算叶子结点个数
int countLeafNodes(BiTree root) {
if (root == NULL) {
return 0;
} else if (root->lchild == NULL && root->rchild == NULL) {
return 1;
} else {
return countLeafNodes(root->lchild) + countLeafNodes(root->rchild);
}
}
// 判断结点是否为叶子结点,并输出路径
int isLeafNode(BiTree root, char data, char path[]) {
if (root == NULL) {
return 0;
} else if (root->data == data) {
path[0] = root->data;
path[1] = '\0';
return 1;
} else {
if (isLeafNode(root->lchild, data, path + 1) || isLeafNode(root->rchild, data, path + 1)) {
path[0] = root->data;
return 1;
} else {
return 0;
}
}
}
int main() {
BiTree root;
char ch;
printf("请输入二叉树的孩子链表表示法:\n");
createBiTree(&root);
getchar(); // 吃掉输入缓冲区中的回车符
printf("该二叉树的叶子结点个数为:%d\n", countLeafNodes(root));
printf("请输入要查找的结点数据:\n");
scanf("%c", &ch);
getchar(); // 吃掉输入缓冲区中的回车符
char path[100];
if (isLeafNode(root, ch, path)) {
printf("%c的路径为:%s\n", ch, path);
} else {
printf("%c不是叶子结点!\n", ch);
}
return 0;
}
```
其中,`createBiTree()` 函数用于创建二叉树,输入时以先序遍历的方式输入,空结点用 `#` 表示。`countLeafNodes()` 函数用于计算二叉树中叶子结点的个数。`isLeafNode()` 函数用于判断指定的结点是否为叶子结点,并输出叶子结点到根结点的路径。
阅读全文