《数据结构（C语言版）第二版》第五章-树和二叉树（5.8 案例分析与实现）

5.8 案例分析与实现

利用二叉树求解表达式的值

表达式树的创建

#include <stdio.h>
#include <stdlib.h>//定义表达树
typedef struct BiTNode
{char data;struct BiTNode* lchild;struct BiTNode* rchild;
}BiTNode, * BiTree;//定义操作符栈
typedef struct OPTRSNode
{char Operator;struct OPTRSNode* next;
}OPTRSNode,*OPTRLStack;//定义表达树栈
typedef struct EXPTSNode
{BiTree Tree;struct EXPTSNode* next;
}EXPTSNode, * EXPTLStack;//定义枚举值
/* 枚举数据类型中的枚举元素，是常亮，不是变量，因此枚举元素又称为枚举常量。
既然系统已经在声明枚举类型时，指定了ERROR是一种枚举元素（常量），
则如果再对其进行宏定义 #define ERROR 0，不管是否与枚举中定义的值相等，都会出现编译错误。*/
typedef enum {GREATER_THAN = '>',LESS_THAN = '<',EQUAL = '=',ERROR
} Pre;#define MAXSIZE 100void InitOPTRLStack(OPTRLStack& OPTR);
void PushOPTRLStack(OPTRLStack& OPTR, char e);
void PopOPTRLStack(OPTRLStack& OPTR, char& e);
char GettopOPTRLStack(OPTRLStack& OPTR);
void InitEXPTLStack(EXPTLStack& EXPT);
void PushEXPTLStack(EXPTLStack& EXPT, BiTree e);
void PopEXPTLStack(EXPTLStack& EXPT, BiTree& e);
BiTree GettopEXPTLStack(EXPTLStack& EXPT);
void CreateExpTree(BiTree& T, BiTree a, BiTree b, char x);
int In(char ch);
Pre Precede(char x, char y);
void InitExpTree(EXPTLStack& EXPT, char* s);
int getline(char* s, int limit);
void PreOrderTraverse(BiTree& T);
void InOrderTraverse(BiTree& T);
void PosOrderTraverse(BiTree& T);
void FreeTree(BiTree& T);//a+b*(c-d)-e/f#
//a+b*c-d-e/f#
//a*b-c#int main()
{int length = 0;int num = 1;char  s[MAXSIZE];EXPTLStack EXPT = NULL;OPTRLStack OPTR = NULL;BiTree T = NULL;char choice = '\0';while (1){printf("请输入第%d个表达式：", num);length = getline(s, MAXSIZE);InitExpTree(EXPT, s);T = GettopEXPTLStack(EXPT);printf("该表达式树的先序序列为：");PreOrderTraverse(T);printf("\n该表达式树的中序序列为：");InOrderTraverse(T);printf("\n该表达式树的后序序列为：");PosOrderTraverse(T);//释放树的内存FreeTree(T);printf("\n是否继续？（y/n）");scanf_s(" %c", &choice);getchar();if (choice != 'y' && choice != 'Y'){break;}num++;printf("\n\n");}return 0;
}//初始化操作符栈
void InitOPTRLStack(OPTRLStack& OPTR)
{OPTR = NULL;
}//操作符入栈
void PushOPTRLStack(OPTRLStack& OPTR, char e)
{OPTRSNode* p = (OPTRSNode*)malloc(sizeof(OPTRSNode));if (!p){printf("操作符入栈时，内存分配失败。\n");return;}p->Operator = e;p->next = OPTR;OPTR = p;
}//操作符出栈
void PopOPTRLStack(OPTRLStack& OPTR, char& e)
{if (!OPTR){printf("操作符出栈时，栈不存在。\n");return;}OPTRSNode* p = OPTR;e = p->Operator;OPTR = OPTR->next;free(p);
}//取操作符栈栈顶
char GettopOPTRLStack(OPTRLStack& OPTR)
{if (!OPTR){printf("取栈顶操作符时，栈不存在。\n");return '\0';}return OPTR->Operator;
}//初始化表达树栈
void InitEXPTLStack(EXPTLStack& EXPT)
{EXPT = NULL;
}//表达树入栈
void PushEXPTLStack(EXPTLStack& EXPT, BiTree e)
{EXPTSNode* p = (EXPTSNode*)malloc(sizeof(EXPTSNode));if (!p){printf("表达树入栈时，内存分配失败。\n");return;}p->Tree = e;p->next = EXPT;EXPT = p;
}//表达树出栈
void PopEXPTLStack(EXPTLStack& EXPT, BiTree& e)
{if (!EXPT){printf("表达树出栈时，栈不存在。\n");return;}EXPTSNode* p = EXPT;e = p->Tree;EXPT = EXPT->next;free(p);
}//取表达树栈栈顶
BiTree GettopEXPTLStack(EXPTLStack& EXPT)
{if (!EXPT){printf("取表达树栈栈顶时，栈不存在。\n");return NULL;}return EXPT->Tree;
}//以x为根结点的data值，以a为左子树，以b为右子树，创建一棵二叉树T
void CreateExpTree(BiTree& T, BiTree a, BiTree b, char x)
{T = (BiTree)malloc(sizeof(BiTNode));T->data  = x;T->lchild = a;T->rchild = b;
}//判断ch是否是运算符，是则返回1，不是返回0
int In(char ch)
{if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')'|| ch == '#'){return 1;}else{return 0;}
}//比较两个运算符的优先级，输出结果的含义为：x>y  x<y  x=y
Pre Precede(char x, char y)
{//")"与 "("、"＃"与")" 以及"("与"#"相继出现时，报错。if ((x == '(' && y == '#') || (x == ')' && y == '(') || (x == '#' && y == ')')){return ERROR;  //枚举类型中的ERROR;}else if (x == '+' || x == '-') {if (y == '+' || y == '-' || y == ')' || y == '#')return GREATER_THAN;elsereturn LESS_THAN;}else if (x == '*' || x == '/') {if (y == '+' || y == '-' || y == '*' || y == '/' || y == ')' || y == '#')return GREATER_THAN;elsereturn LESS_THAN;}else if (x == '(') {if (y == ')')return EQUAL;elsereturn LESS_THAN;}else if (x == ')')return GREATER_THAN;else {if (y == '#')return  EQUAL;else//当x为#时，y是除"#"及")"【ERROR】的字符时，都返回xiao//当x为空字符时，y无论是什么字符，都返回xiaoreturn LESS_THAN;}
}//算法5.12 表达式树的创建
void InitExpTree(EXPTLStack& EXPT, char *s)
{InitEXPTLStack(EXPT);OPTRLStack OPTR = NULL;InitOPTRLStack(OPTR);int i = 0;char ch = s[i];BiTree T = NULL;char theta = '\0';char x = '\0';BiTree a = NULL;BiTree b = NULL;PushOPTRLStack(OPTR, '#');while (ch != '#' || GettopOPTRLStack(OPTR) != '#'){if(!In(ch)){CreateExpTree(T, NULL, NULL, ch);PushEXPTLStack(EXPT, T);++i;ch = s[i];  //ch = s[++i];}else{switch (Precede(GettopOPTRLStack(OPTR), ch)){case LESS_THAN:PushOPTRLStack(OPTR, ch);++i;ch = s[i];  //ch = s[++i];break;case GREATER_THAN:PopOPTRLStack(OPTR, theta);PopEXPTLStack(EXPT, b);PopEXPTLStack(EXPT, a);CreateExpTree(T, a, b, theta);PushEXPTLStack(EXPT, T);break;case EQUAL:PopOPTRLStack(OPTR, x);++i;ch = s[i]; //ch = s[++i];break;}}}//清空栈while (OPTR) {PopOPTRLStack(OPTR, x);}
}int getline(char* s, int limit)
{int c = 0;int i = 0;for (i = 0; i < limit - 1 && (c = getchar()) != EOF && c != '\n'; i++){s[i] = c;}s[i] = '\0';return i;
}//二叉树的先序遍历
void PreOrderTraverse(BiTree& T)
{if (T){printf("%c", T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}
}//二叉树的中序遍历
void InOrderTraverse(BiTree& T)
{if (T){InOrderTraverse(T->lchild);printf("%c", T->data);InOrderTraverse(T->rchild);}
}//二叉树的后序遍历
void PosOrderTraverse(BiTree& T)
{if (T){PosOrderTraverse(T->lchild);PosOrderTraverse(T->rchild);printf("%c", T->data);}
}// 释放树的内存（这个函数好像没啥用）
void FreeTree(BiTree& T) 
{if (T) {FreeTree(T->lchild);FreeTree(T->rchild);free(T);T = NULL;}
}

表达式树的求值

#include <stdio.h>
#include <stdlib.h>//定义表达树
typedef struct BiTNode
{char data;struct BiTNode* lchild;struct BiTNode* rchild;
}BiTNode, * BiTree;//定义操作符栈
typedef struct OPTRSNode
{char Operator;struct OPTRSNode* next;
}OPTRSNode, * OPTRLStack;//定义表达树栈
typedef struct EXPTSNode
{BiTree Tree;struct EXPTSNode* next;
}EXPTSNode, * EXPTLStack;//定义枚举值
/* 枚举数据类型中的枚举元素，是常亮，不是变量，因此枚举元素又称为枚举常量。
既然系统已经在声明枚举类型时，指定了ERROR是一种枚举元素（常量），
则如果再对其进行宏定义 #define ERROR 0，不管是否与枚举中定义的值相等，都会出现编译错误。*/
typedef enum {GREATER_THAN = '>',LESS_THAN = '<',EQUAL = '=',ERROR
} Pre;#define MAXSIZE 100void InitOPTRLStack(OPTRLStack& OPTR);
void PushOPTRLStack(OPTRLStack& OPTR, char e);
void PopOPTRLStack(OPTRLStack& OPTR, char& e);
char GettopOPTRLStack(OPTRLStack& OPTR);
void InitEXPTLStack(EXPTLStack& EXPT);
void PushEXPTLStack(EXPTLStack& EXPT, BiTree e);
void PopEXPTLStack(EXPTLStack& EXPT, BiTree& e);
BiTree GettopEXPTLStack(EXPTLStack& EXPT);
void CreateExpTree(BiTree& T, BiTree a, BiTree b, char x);
int In(char ch);
Pre Precede(char x, char y);
void InitExpTree(EXPTLStack& EXPT, char* s);
int getline(char* s, int limit);
void PreOrderTraverse(BiTree& T);
void InOrderTraverse(BiTree& T);
void PosOrderTraverse(BiTree& T);
void FreeTree(BiTree& T);
int Operate(int a, char x, int b);
int EvaluateExpTree(BiTree T);int main()
{int length = 0;int num = 1;char  s[MAXSIZE];EXPTLStack EXPT = NULL;OPTRLStack OPTR = NULL;BiTree T = NULL;int result = 0;char choice = '\0';while (1){printf("请输入第%d个表达式：", num);length = getline(s, MAXSIZE);InitExpTree(EXPT, s);T = GettopEXPTLStack(EXPT);printf("该表达式树的先序序列为：");PreOrderTraverse(T);printf("\n该表达式树的中序序列为：");InOrderTraverse(T);printf("\n该表达式树的后序序列为：");PosOrderTraverse(T);result = EvaluateExpTree(T);printf("\n该表达式的计算结果为：%d", result);//释放树的内存FreeTree(T);printf("\n是否继续？（y/n）");scanf_s(" %c", &choice);getchar();if (choice != 'y' && choice != 'Y'){break;}num++;printf("\n\n");}return 0;
}//初始化操作符栈
void InitOPTRLStack(OPTRLStack& OPTR)
{OPTR = NULL;
}//操作符入栈
void PushOPTRLStack(OPTRLStack& OPTR, char e)
{OPTRSNode* p = (OPTRSNode*)malloc(sizeof(OPTRSNode));if (!p){printf("操作符入栈时，内存分配失败。\n");return;}p->Operator = e;p->next = OPTR;OPTR = p;
}//操作符出栈
void PopOPTRLStack(OPTRLStack& OPTR, char& e)
{if (!OPTR){printf("操作符出栈时，栈不存在。\n");return;}OPTRSNode* p = OPTR;e = p->Operator;OPTR = OPTR->next;free(p);
}//取操作符栈栈顶
char GettopOPTRLStack(OPTRLStack& OPTR)
{if (!OPTR){printf("取栈顶操作符时，栈不存在。\n");return '\0';}return OPTR->Operator;
}//初始化表达树栈
void InitEXPTLStack(EXPTLStack& EXPT)
{EXPT = NULL;
}//表达树入栈
void PushEXPTLStack(EXPTLStack& EXPT, BiTree e)
{EXPTSNode* p = (EXPTSNode*)malloc(sizeof(EXPTSNode));if (!p){printf("表达树入栈时，内存分配失败。\n");return;}p->Tree = e;p->next = EXPT;EXPT = p;
}//表达树出栈
void PopEXPTLStack(EXPTLStack& EXPT, BiTree& e)
{if (!EXPT){printf("表达树出栈时，栈不存在。\n");return;}EXPTSNode* p = EXPT;e = p->Tree;EXPT = EXPT->next;free(p);
}//取表达树栈栈顶
BiTree GettopEXPTLStack(EXPTLStack& EXPT)
{if (!EXPT){printf("取表达树栈栈顶时，栈不存在。\n");return NULL;}return EXPT->Tree;
}//以x为根结点的data值，以a为左子树，以b为右子树，创建一棵二叉树T
void CreateExpTree(BiTree& T, BiTree a, BiTree b, char x)
{T = (BiTree)malloc(sizeof(BiTNode));T->data = x;T->lchild = a;T->rchild = b;
}//判断ch是否是运算符，是则返回1，不是返回0
int In(char ch)
{if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#'){return 1;}else{return 0;}
}//比较两个运算符的优先级，输出结果的含义为：x>y  x<y  x=y
Pre Precede(char x, char y)
{//")"与 "("、"＃"与")" 以及"("与"#"相继出现时，报错。if ((x == '(' && y == '#') || (x == ')' && y == '(') || (x == '#' && y == ')')){return ERROR;  //枚举类型中的ERROR;}else if (x == '+' || x == '-') {if (y == '+' || y == '-' || y == ')' || y == '#')return GREATER_THAN;elsereturn LESS_THAN;}else if (x == '*' || x == '/') {if (y == '+' || y == '-' || y == '*' || y == '/' || y == ')' || y == '#')return GREATER_THAN;elsereturn LESS_THAN;}else if (x == '(') {if (y == ')')return EQUAL;elsereturn LESS_THAN;}else if (x == ')')return GREATER_THAN;else {if (y == '#')return  EQUAL;else//当x为#时，y是除"#"及")"【ERROR】的字符时，都返回xiao//当x为空字符时，y无论是什么字符，都返回xiaoreturn LESS_THAN;}
}//算法5.12 表达式树的创建
void InitExpTree(EXPTLStack& EXPT, char* s)
{InitEXPTLStack(EXPT);OPTRLStack OPTR = NULL;InitOPTRLStack(OPTR);int i = 0;char ch = s[i];BiTree T = NULL;char theta = '\0';char x = '\0';BiTree a = NULL;BiTree b = NULL;PushOPTRLStack(OPTR, '#');while (ch != '#' || GettopOPTRLStack(OPTR) != '#'){if (!In(ch)){CreateExpTree(T, NULL, NULL, ch);PushEXPTLStack(EXPT, T);++i;ch = s[i];  //ch = s[++i];}else{switch (Precede(GettopOPTRLStack(OPTR), ch)){case LESS_THAN:PushOPTRLStack(OPTR, ch);++i;ch = s[i];  //ch = s[++i];break;case GREATER_THAN:PopOPTRLStack(OPTR, theta);PopEXPTLStack(EXPT, b);PopEXPTLStack(EXPT, a);CreateExpTree(T, a, b, theta);PushEXPTLStack(EXPT, T);break;case EQUAL:PopOPTRLStack(OPTR, x);++i;ch = s[i];  //ch = s[++i];break;}}}//清空栈while (OPTR){PopOPTRLStack(OPTR, x);}
}int getline(char* s, int limit)
{int c = 0;int i = 0;for (i = 0; i < limit - 1 && (c = getchar()) != EOF && c != '\n'; i++){s[i] = c;}s[i] = '\0';return i;
}//二叉树的先序遍历
void PreOrderTraverse(BiTree& T)
{if (T){printf("%c ", T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}
}//二叉树的中序遍历
void InOrderTraverse(BiTree& T)
{if (T){InOrderTraverse(T->lchild);printf("%c ", T->data);InOrderTraverse(T->rchild);}
}//二叉树的后序遍历
void PosOrderTraverse(BiTree& T)
{if (T){PosOrderTraverse(T->lchild);PosOrderTraverse(T->rchild);printf("%c ", T->data);}
}// 释放树的内存（这个函数好像没啥用）
void FreeTree(BiTree& T)
{if (T){FreeTree(T->lchild);FreeTree(T->rchild);free(T);T = NULL;}
}//针对数值，操作数a、b只能是[0,9]的一位数数字，
//计算结果返回值result只能是[-128,127的]区间内的255个值。且大于一位的，打印输出时要选择printf的参数是"%d"，而不能是"%c".
int Operate(int a, char x, int b)
{int result = '0';  if (x == '+'){result = a + b ;}else if (x == '-'){result = a - b;}else if (x == '*'){result = a * b;}else{if (b != 0){result = a / b;}else{printf("除数不能为0");return -184656324;}}return result;
}int EvaluateExpTree(BiTree T)
{int lvalue = 0;int rvalue = 0;int result = 0;if (T->lchild == NULL && T->rchild == NULL){//printf("\nT = %c", T->data);result = T->data - '0';}else{//printf("\nT->lchild = %c", T->lchild->data);//printf("\nT->rchild = %c", T->rchild->data);lvalue = EvaluateExpTree(T->lchild);rvalue = EvaluateExpTree(T->rchild);result = Operate(lvalue, T->data, rvalue);}//printf("\nresult = %d", result);return result;
}