假设二叉树中的所有节点值为int类型,采用二叉链表存储。用c语言设计完整代码递归算法求二叉树bt中从根结点到叶子结点路径和最大的一条路径。
时间: 2024-03-01 12:50:35 浏览: 121
erchashubianli.rar_用二叉链表 进行 二叉树 遍历
好的,这里是完整代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
Node* createNode(int data) {
Node *node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
Node* createBinaryTree() {
Node *root = createNode(10);
root->left = createNode(5);
root->right = createNode(-3);
root->left->left = createNode(3);
root->left->right = createNode(2);
root->right->right = createNode(11);
root->left->left->left = createNode(3);
root->left->left->right = createNode(-2);
root->left->right->right = createNode(1);
return root;
}
int maxPathSum(Node *root, int *maxSum) {
if (root == NULL) {
return 0;
}
int leftSum = maxPathSum(root->left, maxSum);
int rightSum = maxPathSum(root->right, maxSum);
int pathSum = root->data + (leftSum > 0 ? leftSum : 0) + (rightSum > 0 ? rightSum : 0);
if (pathSum > *maxSum) {
*maxSum = pathSum;
}
return root->data + (leftSum > rightSum ? leftSum : rightSum);
}
int main() {
Node *root = createBinaryTree();
int maxSum = maxPathSum(root, &maxSum);
printf("Max path sum: %d\n", maxSum);
return 0;
}
```
在main函数中,我们先调用createBinaryTree函数来创建一个二叉树,并且将根节点传入maxPathSum函数中计算路径和最大的一条路径的路径和。最后输出计算结果。
阅读全文