题目
设计算法，将给定表达式树转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。
思想
中序递归遍历，当遍历到是操作符的非头结点时，在开头加左括号，结尾加右括号。
代码
void midSubTree(BTree T) {
if (T->left != NULL || T->right != NULL) {
printf("( ");
if (T->left != NULL)
midSubTree(T->left);
printf("%c ", T->data);
if (T->right != NULL)
midSubTree(T->right);
printf(") ");
}
else
printf("%c ", T->data);
}
void midTree(BTree T) {
if (T->left!=NULL)
midSubTree(T->left);
printf("%c ", T->data);
if (T->right != NULL)
midSubTree(T->right);
}
运行结果
int main() {
BTree root;
creatNode(root, '*');
BTNode *l;
creatNode(l, '+');
BTNode *l1;
creatNode(l1, 'a');
BTNode *l2;
creatNode(l2, 'b');
l->left = l1;
l->right = l2;
BTNode *r;
creatNode(r, '*');
BTNode *r1;
creatNode(r1, 'c');
BTNode *r2;
creatNode(r2, '-');
BTNode *r3;
creatNode(r3, 'd');
r2->right = r3;
r->left = r1;
r->right = r2;
root->left = l;
root->right = r;
midTree(root);
return 0;
}
捕获4.PNG
其他代码
#include<stdio.h>
#include<stdlib.h>
typedef struct node {
struct node *left;
struct node *right;
char data;
}BTNode, *BTree;
void creatNode(BTree &T, char ch) {
T = (BTNode*)malloc(sizeof(BTNode));
T->data = ch;
T->left = NULL;
T->right = NULL;
}
