c语言实现一个函数,输出二叉树表示的表达式的后缀式。
时间: 2023-06-09 14:05:14 浏览: 117
好的,这是一个具体的编程问题,以下是一个简单的C语言实现,希望能够帮到你。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
// 定义二叉树结构体
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 定义栈结构体
typedef struct Stack {
TreeNode *data[MAX_SIZE];
int top;
} Stack;
void initStack(Stack *s) {
s->top = -1;
}
void push(Stack *s, TreeNode *node) {
if (s->top == MAX_SIZE - 1) {
return;
}
s->data[++s->top] = node;
}
TreeNode *pop(Stack *s) {
if (s->top == -1) {
return NULL;
}
return s->data[s->top--];
}
int isOperator(char c) {
if (c == '+' || c == '-' || c == '*' || c == '/') {
return 1;
}
return 0;
}
TreeNode* createNode(char c) {
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = c;
node->left = node->right = NULL;
return node;
}
void buildTree(char *str, TreeNode **root) {
Stack s;
initStack(&s);
int len = strlen(str);
for (int i = 0; i < len; i++) {
if (isOperator(str[i])) {
TreeNode *node = createNode(str[i]);
node->right = pop(&s);
node->left = pop(&s);
push(&s, node);
} else {
push(&s, createNode(str[i]));
}
}
*root = pop(&s);
}
void postorderTraversal(TreeNode *node) {
if (node == NULL) {
return;
}
postorderTraversal(node->left);
postorderTraversal(node->right);
printf("%c ", node->data);
}
void postfixExpression(char *str) {
TreeNode *tree = NULL;
buildTree(str, &tree);
postorderTraversal(tree);
}
int main() {
char str[] = "ab+cde+**";
postfixExpression(str);
return 0;
}
```
这个程序实现了通过字符串表示二叉树表达式,构建二叉树,并输出后缀式。其中主要的函数是`buildTree`和`postorderTraversal`,`buildTree`函数通过输入的字符串构建出二叉树,而`postorderTraversal`函数则是完成二叉树的后序遍历并输出后缀式。
阅读全文