后缀表达式用二叉树计算的例子和C代码
时间: 2024-05-06 10:17:44 浏览: 4
以下是一个后缀表达式用二叉树计算的例子:
后缀表达式:3 4 + 5 *
对应的二叉树:
```
*
/ \
+ 5
/ \
3 4
```
按照后序遍历的顺序计算二叉树,得到结果 35。
以下是相应的 C 代码实现:
```c
#include <stdlib.h>
#include <stdio.h>
// 定义二叉树节点
typedef struct node {
char data;
struct node *left, *right;
} Node;
// 创建节点
Node* createNode(char data) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// 构建二叉树
Node* buildTree(char postfix[]) {
Node* stack[100];
int top = -1, i;
for (i = 0; postfix[i] != '\0'; i++) {
Node* newNode = createNode(postfix[i]);
if (postfix[i] >= '0' && postfix[i] <= '9') {
stack[++top] = newNode;
} else {
newNode->right = stack[top--];
newNode->left = stack[top--];
stack[++top] = newNode;
}
}
return stack[top];
}
// 后序遍历二叉树并计算结果
int evaluate(Node* root) {
if (root) {
int leftVal = evaluate(root->left);
int rightVal = evaluate(root->right);
switch (root->data) {
case '+': return leftVal + rightVal;
case '-': return leftVal - rightVal;
case '*': return leftVal * rightVal;
case '/': return leftVal / rightVal;
default: return root->data - '0';
}
}
}
int main() {
char postfix[] = "34+5*";
Node* root = buildTree(postfix);
int result = evaluate(root);
printf("The result is: %d\n", result);
return 0;
}
```