输入一个表达式(表达式中的数均为小于10的正整数),利用二叉树来表示该表达式,创建表达式树,然后利用二叉树的遍历操作求表达式的值。使用c语言,并且每条代码都需要注释
时间: 2025-02-05 20:12:08 浏览: 60
好的,下面是一个使用C语言实现的程序,该程序可以输入一个表达式(表达式中的数均为小于10的正整数),利用二叉树来表示该表达式,创建表达式树,然后利用二叉树的遍历操作求表达式的值。每条代码都附有注释。
```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* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 判断字符是否为运算符
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
// 构建表达式树
TreeNode* buildExpressionTree(char* postfix) {
TreeNode* stack[100];
int top = -1;
for (int i = 0; postfix[i] != '\0'; i++) {
if (isdigit(postfix[i])) {
// 如果是数字,则创建一个新节点并压入栈中
stack[++top] = createNode(postfix[i]);
} else if (isOperator(postfix[i])) {
// 如果是运算符,则创建一个新节点,并从栈中弹出两个节点作为其子节点
TreeNode* node = createNode(postfix[i]);
node->right = stack[top--];
node->left = stack[top--];
stack[++top] = node; // 将新节点压入栈中
}
}
return stack[top]; // 返回根节点
}
// 计算表达式树的值
int evaluateExpressionTree(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return root->data - '0'; // 如果是叶子节点,则返回其数值
}
// 递归计算左子树和右子树的值
int leftVal = evaluateExpressionTree(root->left);
int rightVal = evaluateExpressionTree(root->right);
// 根据运算符计算当前节点的值
switch (root->data) {
case '+': return leftVal + rightVal;
case '-': return leftVal - rightVal;
case '*': return leftVal * rightVal;
case '/': return leftVal / rightVal;
default: return 0;
}
}
// 中序遍历表达式树
void inorder(TreeNode* root) {
if (root != NULL) {
inorder(root->left);
printf("%c", root->data);
inorder(root->right);
}
}
// 主函数
int main() {
char postfix[100];
printf("请输入后缀表达式(数字和运算符之间用空格分隔):\n");
fgets(postfix, sizeof(postfix), stdin);
// 构建表达式树
TreeNode* root = buildExpressionTree(postfix);
// 计算表达式的值
int result = evaluateExpressionTree(root);
printf("表达式的值为:%d\n", result);
// 中序遍历表达式树
printf("中序遍历表达式树的结果为:");
inorder(root);
printf("\n");
return 0;
}
```
这个程序首先定义了一个二叉树节点结构 `TreeNode`,然后实现了创建新节点、判断字符是否为运算符、构建表达式树、计算表达式树的值以及中序遍历表达式树的功能。
阅读全文
相关推荐
















