再结合以上内容,设计函数实现如下功能:给定结点数据(如字符“E”),判断其是否为叶子结点。如果是则输出叶子结点到根结点的路径。
时间: 2024-02-06 15:12:30 浏览: 18
好的,我们可以改进上面的代码,添加一个函数来实现这个功能。具体实现思路如下:
1. 遍历孩子链表,找到目标节点,并记录路径上的所有节点。
2. 如果目标节点是叶子节点,则输出路径上的所有节点。
3. 如果目标节点不是叶子节点,则返回空路径。
下面是具体的代码实现:
```c
void find_path(ChildNode *cur, int target, int *path, int *len) {
if (cur == NULL) {
return;
}
path[*len] = cur->data;
(*len)++;
if (cur->data == target) {
return;
}
ChildNode *child = cur->next;
while (child != NULL) {
find_path(get_node(child->data), target, path, len);
if (path[*len - 1] == target) {
return;
}
(*len)--;
child = child->next;
}
}
void print_path(int *path, int len) {
for (int i = len - 1; i >= 0; i--) {
printf("%d ", path[i]);
}
printf("\n");
}
void is_leaf_node(int target) {
int path[100];
int len = 0;
find_path(clist->head, target, path, &len);
if (is_leaf(get_node(target))) {
printf("该节点是叶子节点,路径为:");
print_path(path, len);
} else {
printf("该节点不是叶子节点\n");
}
}
int is_leaf(Node *node) {
return node != NULL && node->left == NULL && node->right == NULL;
}
Node *get_node(int target) {
// 这里假设二叉树中的数据都是唯一的
if (tree == NULL) {
return NULL;
} else if (tree->data == target) {
return tree;
} else {
Node *left_node = get_node(target, tree->left);
if (left_node != NULL) {
return left_node;
} else {
return get_node(target, tree->right);
}
}
}
Node *get_node(int target, Node *cur) {
if (cur == NULL) {
return NULL;
} else if (cur->data == target) {
return cur;
} else {
Node *left_node = get_node(target, cur->left);
if (left_node != NULL) {
return left_node;
} else {
return get_node(target, cur->right);
}
}
}
```
完整代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
typedef struct child_node {
int data;
struct child_node *next;
} ChildNode;
typedef struct child_list {
ChildNode *head;
} ChildList;
Node *tree;
ChildList *clist;
void input_tree(Node *tree, ChildList *clist);
int count_leaves(ChildNode *head);
void is_leaf_node(int target);
void find_path(ChildNode *cur, int target, int *path, int *len);
void print_path(int *path, int len);
int is_leaf(Node *node);
Node *get_node(int target);
Node *get_node(int target, Node *cur);
int main() {
// 构造一棵二叉树
tree = (Node *)malloc(sizeof(Node));
tree->data = 1;
tree->left = (Node *)malloc(sizeof(Node));
tree->left->data = 2;
tree->left->left = NULL;
tree->left->right = NULL;
tree->right = (Node *)malloc(sizeof(Node));
tree->right->data = 3;
tree->right->left = (Node *)malloc(sizeof(Node));
tree->right->left->data = 4;
tree->right->left->left = NULL;
tree->right->left->right = NULL;
tree->right->right = (Node *)malloc(sizeof(Node));
tree->right->right->data = 5;
tree->right->right->left = NULL;
tree->right->right->right = NULL;
// 将二叉树以孩子链表表示法输入到计算机中
clist = (ChildList *)malloc(sizeof(ChildList));
clist->head = NULL;
input_tree(tree, clist);
// 计算叶子结点个数
int count = count_leaves(clist->head);
printf("叶子结点个数为:%d\n", count);
// 判断指定节点是否是叶子节点,并输出路径
is_leaf_node(5);
return 0;
}
void input_tree(Node *tree, ChildList *clist) {
if (tree == NULL) {
return;
}
ChildNode *new_child_node = (ChildNode *)malloc(sizeof(ChildNode));
new_child_node->data = tree->data;
new_child_node->next = NULL;
if (clist->head == NULL) {
clist->head = new_child_node;
} else {
ChildNode *cur = clist->head;
while (cur->next != NULL) {
cur = cur->next;
}
cur->next = new_child_node;
}
input_tree(tree->left, clist);
input_tree(tree->right, clist);
}
int count_leaves(ChildNode *head) {
if (head == NULL) {
return 0;
}
if (head->next == NULL) {
return 1;
}
int count = 0;
ChildNode *cur = head;
while (cur != NULL) {
count += count_leaves(cur->next);
cur = cur->next;
}
return count;
}
void is_leaf_node(int target) {
int path[100];
int len = 0;
find_path(clist->head, target, path, &len);
if (is_leaf(get_node(target))) {
printf("该节点是叶子节点,路径为:");
print_path(path, len);
} else {
printf("该节点不是叶子节点\n");
}
}
void find_path(ChildNode *cur, int target, int *path, int *len) {
if (cur == NULL) {
return;
}
path[*len] = cur->data;
(*len)++;
if (cur->data == target) {
return;
}
ChildNode *child = cur->next;
while (child != NULL) {
find_path(get_node(child->data), target, path, len);
if (path[*len - 1] == target) {
return;
}
(*len)--;
child = child->next;
}
}
void print_path(int *path, int len) {
for (int i = len - 1; i >= 0; i--) {
printf("%d ", path[i]);
}
printf("\n");
}
int is_leaf(Node *node) {
return node != NULL && node->left == NULL && node->right == NULL;
}
Node *get_node(int target) {
// 这里假设二叉树中的数据都是唯一的
if (tree == NULL) {
return NULL;
} else if (tree->data == target) {
return tree;
} else {
Node *left_node = get_node(target, tree->left);
if (left_node != NULL) {
return left_node;
} else {
return get_node(target, tree->right);
}
}
}
Node *get_node(int target, Node *cur) {
if (cur == NULL) {
return NULL;
} else if (cur->data == target) {
return cur;
} else {
Node *left_node = get_node(target, cur->left);
if (left_node != NULL) {
return left_node;
} else {
return get_node(target, cur->right);
}
}
}
```