后缀表达式用二叉树计算的例子和C代码
时间: 2024-05-13 09:18:27 浏览: 19
下面是一个后缀表达式用二叉树计算的例子:
假设我们有一个后缀表达式为 "5 2 +",我们可以使用一棵二叉树来计算它。首先,我们将数字 5 放入树的左节点,数字 2 放入右节点,然后将 "+" 操作符放入父节点。最终的二叉树如下所示:
```
+
/ \
5 2
```
接下来,我们可以通过遍历这棵树来计算它的值。从根节点开始,我们遇到了操作符 "+",于是我们将左节点的值 5 和右节点的值 2 相加得到 7,将结果存放在父节点中。这样我们就得到了表达式的结果。
下面是用C语言实现上述计算过程的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
struct node {
char data;
struct node *left;
struct node *right;
};
// 创建一个新的节点
struct node *create_node(char data) {
struct node *new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
// 构建表达式二叉树
struct node *build_expression_tree(char postfix[]) {
struct node *stack[100];
int top = -1;
for (int i = 0; postfix[i] != '\0'; i++) {
char ch = postfix[i];
if (isdigit(ch)) {
stack[++top] = create_node(ch);
} else {
struct node *new_node = create_node(ch);
new_node->right = stack[top--];
new_node->left = stack[top--];
stack[++top] = new_node;
}
}
return stack[top];
}
// 计算表达式树的值
int evaluate_expression_tree(struct node *root) {
if (root == NULL) {
return 0;
}
if (isdigit(root->data)) {
return root->data - '0';
}
int left_operand = evaluate_expression_tree(root->left);
int right_operand = evaluate_expression_tree(root->right);
switch (root->data) {
case '+': return left_operand + right_operand;
case '-': return left_operand - right_operand;
case '*': return left_operand * right_operand;
case '/': return left_operand / right_operand;
}
return 0;
}
int main() {
char postfix[] = "52+";
struct node *root = build_expression_tree(postfix);
printf("Result: %d\n", evaluate_expression_tree(root));
return 0;
}
```
在上面的代码中,`build_expression_tree`函数用于构建表达式二叉树,`evaluate_expression_tree`函数用于计算表达式树的值。我们可以使用这些函数来计算任意后缀表达式的值。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)