C语言计算“孩子链表表示法”下二叉树的叶子结点个数,给定结点数据(如字符“E”),判断其是否为叶子结点。如果是则输出叶子结点到根结点的路径。
时间: 2024-02-03 21:13:56 浏览: 71
首先,我们需要定义“孩子链表表示法”下二叉树的结构体:
```c
typedef struct TreeNode {
char data; // 存储节点数据
struct TreeNode *left_child; // 左孩子节点
struct TreeNode *right_sibling; // 右兄弟节点
} TreeNode;
```
其中,`left_child` 指向该节点的左孩子,`right_sibling` 指向该节点的右兄弟。如果没有左孩子或右兄弟,则相应指针为 `NULL`。
现在,我们可以编写计算二叉树叶子节点个数的函数:
```c
int count_leaf_nodes(TreeNode *root) {
if (root == NULL) {
return 0;
} else if (root->left_child == NULL) {
return 1 + count_leaf_nodes(root->right_sibling);
} else {
return count_leaf_nodes(root->left_child) + count_leaf_nodes(root->right_sibling);
}
}
```
该函数采用递归的方式,计算给定二叉树的叶子节点个数。如果当前节点为空,则返回 0;如果当前节点没有左孩子,则其为叶子节点,返回 1 加上右兄弟的叶子节点个数;否则,递归计算左孩子和右兄弟的叶子节点个数之和。
接下来,我们可以编写判断给定节点是否为叶子节点,并输出叶子节点到根节点的路径的函数:
```c
int is_leaf_node(TreeNode *root, char data) {
if (root == NULL) {
return 0;
} else if (root->data == data && root->left_child == NULL) {
printf("%c", root->data);
return 1;
} else if (is_leaf_node(root->left_child, data)) {
printf(" -> %c", root->data);
return 1;
} else if (is_leaf_node(root->right_sibling, data)) {
printf(" -> %c", root->data);
return 1;
} else {
return 0;
}
}
```
该函数同样采用递归的方式,判断给定节点是否为叶子节点,如果是,则输出叶子节点到根节点的路径,并返回 1;否则,递归判断其左孩子和右兄弟。
注意,在调用该函数时,需要从根节点开始搜索:
```c
TreeNode *root = /* 构造二叉树 */;
char data = 'E';
if (is_leaf_node(root, data)) {
printf("\n");
} else {
printf("%c 不是叶子节点\n", data);
}
```
完整代码如下:
阅读全文