用c语言通过二叉链表遍历根据简单的算术表达式,构造出对应的二叉树,并计算表达式的值,并注释每一行代码。
时间: 2024-02-22 10:56:52 浏览: 72
好,我会尽力解答您的问题。首先,我们需要了解二叉树的基本知识。二叉树是一种树形结构,它的每个节点最多有两个子节点:左子节点和右子节点。而二叉链表是一种链式存储结构,它通过指针来表示节点之间的关系。
在使用二叉链表构造二叉树时,我们可以通过递归地方式来构造。具体来说,我们可以遍历表达式,遇到数字就创建一个叶子节点,遇到运算符就创建一个根节点,并将左右子树分别递归构造。最后,返回根节点即可。
接下来,我们来看一下如何计算表达式的值。我们可以通过递归地方式来计算。具体来说,对于每个节点,如果它是叶子节点,则返回它的值;否则,根据运算符将左右子树的值进行相应的运算,然后返回结果。
下面是用 C 语言实现从表达式构造二叉树并计算表达式值的代码,带有详细的注释:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
char data; // 节点的数据,存储运算符或操作数
struct TreeNode *left; // 左子树指针
struct TreeNode *right;// 右子树指针
} TreeNode, *TreeNodePtr;
// 函数声明
TreeNodePtr createTree(); // 根据表达式创建二叉树
double evaluateTree(TreeNodePtr root); // 计算表达式的值
void destroyTree(TreeNodePtr root); // 销毁二叉树
void printTree(TreeNodePtr root, int depth); // 打印二叉树
int main() {
TreeNodePtr root = createTree(); // 创建二叉树
if (root == NULL) {
printf("Error: invalid expression!\n");
return 1;
}
printTree(root, 0); // 打印二叉树
double result = evaluateTree(root); // 计算表达式的值
printf("Result: %.2f\n", result);
destroyTree(root); // 销毁二叉树
return 0;
}
// 根据表达式创建二叉树
TreeNodePtr createTree() {
char c = getchar();
if (c == EOF) { // 如果表达式已经结束,则返回 NULL
return NULL;
}
TreeNodePtr node = (TreeNodePtr)malloc(sizeof(TreeNode));
if (isdigit(c)) { // 如果是数字,创建叶子节点
node->data = c - '0'; // 将字符转换为数字
node->left = NULL;
node->right = NULL;
} else if (c == '+' || c == '-' || c == '*' || c == '/') { // 如果是运算符,创建根节点
node->data = c;
node->left = createTree(); // 递归创建左子树
node->right = createTree(); // 递归创建右子树
} else { // 如果是其他字符,表示表达式有误,返回 NULL
free(node);
node = NULL;
}
return node;
}
// 计算表达式的值
double evaluateTree(TreeNodePtr root) {
if (root == NULL) { // 如果节点为空,返回 0
return 0;
}
if (root->left == NULL && root->right == NULL) { // 如果是叶子节点,返回节点的值
return root->data;
}
double left = evaluateTree(root->left); // 递归计算左子树的值
double right = evaluateTree(root->right); // 递归计算右子树的值
switch (root->data) { // 根据运算符计算结果
case '+':
return left + right;
case '-':
return left - right;
case '*':
return left * right;
case '/':
return left / right;
default:
return 0;
}
}
// 销毁二叉树
void destroyTree(TreeNodePtr root) {
if (root == NULL) {
return;
}
destroyTree(root->left); // 递归销毁左子树
destroyTree(root->right); // 递归销毁右子树
free(root); // 销毁当前节点
}
// 打印二叉树
void printTree(TreeNodePtr root, int depth) {
if (root == NULL) {
return;
}
printTree(root->right, depth + 1); // 递归打印右子树
printf("%*c%c\n", depth * 4, ' ', root->data); // 打印当前节点
printTree(root->left, depth + 1); // 递归打印左子树
}
```
以上就是用 C 语言通过二叉链表遍历根据简单的算术表达式,构造出对应的二叉树,并计算表达式的值,并注释每一行代码的实现方法。希望能够帮助到您!
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)