用C语言实现二叉树的路径
时间: 2024-05-15 18:15:41 浏览: 11
以下是用C语言实现二叉树路径的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *left;
struct node *right;
} node;
node* create_node(int data) {
node *new_node = (node*)malloc(sizeof(node));
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
void insert_node(node **root, int data) {
if (*root == NULL) {
*root = create_node(data);
return;
}
if (data < (*root)->data) {
insert_node(&(*root)->left, data);
} else {
insert_node(&(*root)->right, data);
}
}
void print_path(int path[], int path_len) {
for (int i = 0; i < path_len; i++) {
printf("%d ", path[i]);
}
printf("\n");
}
void find_path(node *root, int path[], int path_len, int sum) {
if (root == NULL) {
return;
}
path[path_len] = root->data;
path_len++;
sum -= root->data;
if (root->left == NULL && root->right == NULL && sum == 0) {
print_path(path, path_len);
return;
}
find_path(root->left, path, path_len, sum);
find_path(root->right, path, path_len, sum);
}
int main() {
node *root = NULL;
int path[100];
int path_len = 0;
int sum;
insert_node(&root, 5);
insert_node(&root, 3);
insert_node(&root, 7);
insert_node(&root, 1);
insert_node(&root, 4);
insert_node(&root, 6);
insert_node(&root, 8);
printf("Enter the sum: ");
scanf("%d", &sum);
printf("Paths of sum %d:\n", sum);
find_path(root, path, path_len, sum);
return 0;
}
```
在上面的示例代码中,我们定义了一个二叉树的节点结构体,并定义了创建节点和插入节点的函数。我们还定义了一个打印路径的函数。
在`find_path`函数中,我们使用深度优先搜索来遍历二叉树,并将遍历到的节点的值保存在`path`数组中。每当我们遍历到一个叶子节点时,我们检查累加和是否等于给定的`sum`值。如果是,则打印路径。否则,我们继续遍历左右子树。
在`main`函数中,我们创建了一个二叉树,并接收用户输入的`sum`值。我们然后调用`find_path`函数来查找所有路径。如果存在路径,则打印路径。如果没有,则不打印任何东西。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)