使用c语言通过二叉链表输入简单算术表达式,利用 二叉树来表示,并在创建表 达式树后求 表达式的值,注释每一行代码,写出逻辑结构存储结构,核心代码是什么
时间: 2023-12-20 22:03:49 浏览: 94
基于二叉链表构建二叉树.txt
以下是使用 C 语言通过二叉链表输入简单算术表达式,利用二叉树来表示,并在创建表达式树后求表达式的值的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
char data; // 节点存储的数据,可以是操作符或操作数
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
} TreeNode;
// 创建二叉树节点
TreeNode *createNode(char data) {
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->data = data;
node->left = node->right = NULL;
return node;
}
// 创建表达式树
TreeNode *createExpressionTree(char *expression, int *index) {
// 读取一个字符
char c = expression[(*index)++];
// 如果是操作数,创建叶子节点并返回
if (isdigit(c)) {
return createNode(c);
}
// 如果是操作符,创建当前节点,并递归创建左右子树
TreeNode *node = createNode(c);
node->left = createExpressionTree(expression, index);
node->right = createExpressionTree(expression, index);
return node;
}
// 计算表达式树的值
int evaluateExpressionTree(TreeNode *root) {
// 如果是叶子节点,返回节点存储的操作数
if (root->left == NULL && root->right == NULL) {
return root->data - '0';
}
// 计算左右子树的值
int leftValue = evaluateExpressionTree(root->left);
int rightValue = evaluateExpressionTree(root->right);
// 根据操作符计算结果
switch (root->data) {
case '+':
return leftValue + rightValue;
case '-':
return leftValue - rightValue;
case '*':
return leftValue * rightValue;
case '/':
return leftValue / rightValue;
default:
return 0;
}
}
int main() {
// 输入表达式
char expression[100];
printf("请输入表达式:");
scanf("%s", expression);
// 创建表达式树
int index = 0;
TreeNode *root = createExpressionTree(expression, &index);
// 计算表达式树的值
int result = evaluateExpressionTree(root);
printf("表达式的值为:%d\n", result);
return 0;
}
```
逻辑结构:本程序使用二叉树作为数据结构来表示算术表达式,每个节点可以存储操作符或操作数。每个操作符节点都有左右子树,而每个操作数节点都是叶子节点,没有子树。
存储结构:本程序使用二叉链表来存储二叉树,即每个节点包含指向左右子树的指针。
核心代码:本程序的核心代码是 `createExpressionTree` 函数和 `evaluateExpressionTree` 函数。`createExpressionTree` 函数递归地创建表达式树,它从表达式字符串中读取一个字符,如果是操作数则创建叶子节点,否则创建当前节点,并递归创建左右子树。`evaluateExpressionTree` 函数递归地计算表达式树的值,如果是叶子节点则返回节点存储的操作数,否则计算左右子树的值,并根据操作符计算结果。
阅读全文