用c语言建立一个二叉树,节点上全是正整数,要求实现以下功能:求所有节点之和;求出每层节点之和;输出从根节点到叶节点的最长路径和最短路径;输出从根节点到叶节点的路径中和最大的那条
时间: 2024-05-02 20:23:30 浏览: 91
好的,我会根据您的要求来回答问题,不用担心,我不会透露任何信息。
对于您的问题,我来简单介绍一下二叉树。
二叉树是一种树形结构,每个节点最多有两个子节点,分别称为左子节点和右子节点。根节点是二叉树的顶部节点,它没有父节点。叶子节点是没有子节点的节点。二叉树通常用来存储有层级关系的数据。
现在,我来回答您的问题。
首先,我们需要定义一个二叉树节点的结构体,包括节点的值、左子节点和右子节点等信息。下面是一个示例代码:
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
```
接下来,为了方便操作,我们可以定义一个二叉树的结构体,包括根节点和其他一些信息:
```c
struct Tree {
struct TreeNode *root;
int depth;
};
```
其中,depth 表示二叉树的深度,即最大层数。
接下来,我们来逐一实现您提到的功能。
1. 求所有节点之和
这个功能比较简单,可以使用递归来实现。从根节点开始,分别递归遍历左子树和右子树,将每个节点的值加起来即可。
```c
int sum(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
return root->val + sum(root->left) + sum(root->right);
}
```
2. 求出每层节点之和
这个功能也可以使用递归来实现。从根节点开始,每递归一层,就将该层的节点值加起来,直到递归到最后一层为止。
```c
void level_sum(struct TreeNode* root, int level, int* sum) {
if (root == NULL) {
return;
}
sum[level] += root->val;
level_sum(root->left, level + 1, sum);
level_sum(root->right, level + 1, sum);
}
void print_level_sum(struct TreeNode* root) {
int sum[MAX_DEPTH] = {0};
level_sum(root, 0, sum);
for (int i = 0; i < MAX_DEPTH; i++) {
if (sum[i] == 0) {
break;
}
printf("Level %d sum: %d\n", i, sum[i]);
}
}
```
其中,MAX_DEPTH 是一个预定义的最大深度,用来存储每一层节点之和的数组。
3. 输出从根节点到叶节点的最长路径和最短路径
这个功能需要使用深度优先搜索(DFS)来实现。从根节点开始,每次递归时将当前路径的和加上该节点的值。当遇到叶子节点时,将当前路径的和与最长路径和和最短路径和进行比较,更新即可。
```c
void dfs(struct TreeNode* root, int path_sum, int* max_sum, int* min_sum) {
if (root == NULL) {
return;
}
path_sum += root->val;
if (root->left == NULL && root->right == NULL) {
if (path_sum > *max_sum) {
*max_sum = path_sum;
}
if (path_sum < *min_sum) {
*min_sum = path_sum;
}
return;
}
dfs(root->left, path_sum, max_sum, min_sum);
dfs(root->right, path_sum, max_sum, min_sum);
}
void print_longest_shortest_path_sum(struct TreeNode* root) {
int max_sum = INT_MIN, min_sum = INT_MAX;
dfs(root, 0, &max_sum, &min_sum);
printf("Longest path sum: %d\n", max_sum);
printf("Shortest path sum: %d\n", min_sum);
}
```
其中,INT_MIN 和 INT_MAX 是一个预定义的最小值和最大值。
4. 输出从根节点到叶节点的路径中和最大的那条
这个功能也需要使用深度优先搜索(DFS)来实现。从根节点开始,每次递归时将当前路径的和加上该节点的值。当遇到叶子节点时,将当前路径的和与最大路径和进行比较,如果大于最大路径和,就将当前路径保存下来。最后输出保存的那条路径即可。
```c
void dfs2(struct TreeNode* root, int path_sum, int max_sum, int* path, int* max_path) {
if (root == NULL) {
return;
}
path_sum += root->val;
path[max_sum] = root->val;
if (root->left == NULL && root->right == NULL) {
if (path_sum > max_sum) {
max_sum = path_sum;
memcpy(max_path, path, sizeof(int) * (max_sum + 1));
}
return;
}
dfs2(root->left, path_sum, max_sum, path, max_path);
dfs2(root->right, path_sum, max_sum, path, max_path);
}
void print_max_path_sum(struct TreeNode* root) {
int max_sum = INT_MIN;
int path[MAX_DEPTH] = {0};
int max_path[MAX_DEPTH] = {0};
dfs2(root, 0, 0, path, max_path);
printf("Max path sum: %d\n", max_sum);
printf("Max path: ");
for (int i = 0; i < max_sum; i++) {
printf("%d ", max_path[i]);
}
printf("\n");
}
```
好了,以上就是关于用 C 语言建立二叉树并实现相关功能的介绍,希望对您有所帮助。
阅读全文