假设二叉树采用二叉链存储结构存放,结点值为int类型,用c语言设计一个递归算法求二叉树bt中的所有叶子节点值之和
时间: 2023-05-25 14:06:47 浏览: 62
```
int sumOfLeaves(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
// 叶子节点
return root->val;
}
// 非叶子节点
return sumOfLeaves(root->left) + sumOfLeaves(root->right);
}
```
其中,二叉树结点的定义如下:
```
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
解释如下:
1. 若二叉树为空,则叶子节点之和为0,直接返回。
2. 若当前节点为叶子节点,则返回节点值。
3. 若当前节点不是叶子节点,则递归求左子树和右子树的叶子节点之和,并将二者相加返回。
相关问题
用C语言假设二叉树采用二叉链存储结构,设计一个算法输出值为x的结点的所有祖先(结点x唯一)。
以下是用C语言实现的算法,能够输出值为x的结点的所有祖先:
```c
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void Ancestors(BiTree T, int x) {
if (T) {
if (T->data == x) {
return;
}
if (T->lchild && T->lchild->data == x || T->rchild && T->rchild->data == x) {
printf("%d ", T->data);
return;
}
Ancestors(T->lchild, x);
Ancestors(T->rchild, x);
}
}
```
具体实现步骤如下:
1. 判断当前结点 T 是否为空,如果为空则直接返回。
2. 判断当前结点 T 是否为结点 x,如果是,则返回。
3. 判断结点 x 是否在当前结点 T 的左子树或右子树中:
- 如果在左子树或右子树中,则输出当前结点 T 的值,返回。
- 如果不在左子树或右子树中,则递归遍历左子树和右子树。
4. 如果没有找到结点 x,则函数结束。
注意:这里假设二叉树中每个结点的值都不相同。如果有相同的值,需要对代码进行修改。
假设二叉树中的所有节点值为int类型,采用二叉链表存储。用c语言设计完整代码递归算法求二叉树bt中从根结点到叶子结点路径和最大的一条路径。
好的,这里是完整代码:
```
#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函数中计算路径和最大的一条路径的路径和。最后输出计算结果。