用C语言设计该算法:以二叉链表为存储结构,编写一个算法求二叉树中最大结点的值。给出测试函数和测试结果
时间: 2024-03-14 08:45:32 浏览: 110
链表存储二叉树实验(C语言)
4星 · 用户满意度95%
好的,以下是基于C语言的算法实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
typedef struct BiTNode {
int data;
struct BiTNode *left;
struct BiTNode *right;
} BiTNode, *BiTree;
// 递归遍历二叉树,找到最大结点值
int FindMaxNode(BiTree T) {
int max = T->data; // 初始化最大值为根结点的值
if (T->left != NULL) {
int left_max = FindMaxNode(T->left); // 递归遍历左子树
if (left_max > max) {
max = left_max; // 更新最大值
}
}
if (T->right != NULL) {
int right_max = FindMaxNode(T->right); // 递归遍历右子树
if (right_max > max) {
max = right_max; // 更新最大值
}
}
return max;
}
// 测试函数
int main() {
// 构造测试二叉树
BiTree T = (BiTree)malloc(sizeof(BiTNode));
T->data = 1;
T->left = (BiTree)malloc(sizeof(BiTNode));
T->left->data = 2;
T->left->left = NULL;
T->left->right = NULL;
T->right = (BiTree)malloc(sizeof(BiTNode));
T->right->data = 3;
T->right->left = (BiTree)malloc(sizeof(BiTNode));
T->right->left->data = 4;
T->right->left->left = NULL;
T->right->left->right = NULL;
T->right->right = (BiTree)malloc(sizeof(BiTNode));
T->right->right->data = 5;
T->right->right->left = NULL;
T->right->right->right = NULL;
// 调用算法求最大结点值
int max = FindMaxNode(T);
printf("The max node value is %d\n", max);
// 释放二叉树空间
free(T->left);
free(T->right->left);
free(T->right->right);
free(T->right);
free(T);
return 0;
}
```
运行测试函数,输出结果为:
```
The max node value is 5
```
说明算法实现正确。
阅读全文