用C语言编写算法求任意二叉树中一条最长的路径,并输出此路径上各结点的值。
时间: 2024-03-24 19:36:59 浏览: 44
好的,这是一个比较经典的二叉树问题。我可以给你提供一种基于深度优先搜索(DFS)的解法,代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 定义全局变量,用于记录最长路径的长度以及路径上的节点
int max_len = 0;
TreeNode* path[1000];
// 定义深度优先搜索函数
void dfs(TreeNode* root, int depth, TreeNode** cur_path) {
if (root == NULL) {
return;
}
// 将当前节点加入路径
cur_path[depth] = root;
// 如果当前节点是叶子节点
if (root->left == NULL && root->right == NULL) {
// 更新最长路径的长度以及路径上的节点
if (depth > max_len) {
max_len = depth;
for (int i = 0; i <= depth; i++) {
path[i] = cur_path[i];
}
}
}
// 递归搜索左右子树
dfs(root->left, depth + 1, cur_path);
dfs(root->right, depth + 1, cur_path);
}
int main() {
// 构造一个二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->val = 4;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 调用深度优先搜索函数
TreeNode* cur_path[1000];
dfs(root, 0, cur_path);
// 输出最长路径上的节点
printf("The longest path is: ");
for (int i = 0; i <= max_len; i++) {
printf("%d ", path[i]->val);
}
printf("\n");
return 0;
}
```
以上代码实现了一个简单的二叉树结构,其中 `dfs` 函数用于深度优先搜索,`cur_path` 数组用于记录当前搜索路径上的所有节点,`path` 数组用于记录最长路径上的所有节点。在搜索过程中,我们不断更新 `max_len` 和 `path` 数组,以得到最长路径。最后,我们将最长路径上的所有节点输出即可。希望对你有所帮助!
阅读全文