假设二叉树中的每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法,用c语言实现求二叉树中最小值的节点值
时间: 2024-02-09 20:12:54 浏览: 83
好的,以下是基于C语言的二叉树最小值节点的查找算法实现:
```c
#include <stdio.h>
#include <stdlib.h>
/* 定义二叉树节点结构体 */
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
/* 创建二叉树节点 */
TreeNode* createNode(char val) {
TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
/* 二叉树中序遍历查找最小值节点 */
TreeNode* minNode(TreeNode* root) {
TreeNode* minP = NULL;
TreeNode* p = root;
TreeNode* stack[100];
int top = -1;
while (p != NULL || top != -1) {
if (p != NULL) {
stack[++top] = p;
p = p->left;
} else {
TreeNode* node = stack[top--];
if (minP == NULL || node->val < minP->val) {
minP = node;
}
p = node->right;
}
}
return minP;
}
int main() {
/* 创建二叉树 */
TreeNode* root = createNode('5');
root->left = createNode('3');
root->right = createNode('8');
root->left->left = createNode('2');
root->left->right = createNode('4');
root->right->left = createNode('7');
root->right->right = createNode('10');
/* 查找最小值节点 */
TreeNode* minP = minNode(root);
printf("The min node value is: %c\n", minP->val);
return 0;
}
```
该算法首先定义了二叉树节点的数据结构,然后定义了创建二叉树节点的createNode函数。接着定义了minNode函数,该函数使用中序遍历的方式遍历二叉树,并记录最小值节点minP。最后在main函数中创建二叉树并调用minNode函数查找最小值节点。
阅读全文