表达式二叉树

表达式二叉树 一、需求分析 1、对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一棵表达式二叉树，并且图示出来（图形的形式）。 2、对于构造好的内部表达式二叉树，按照用户的要求输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括）或后缀表达式（不带括号）。

二、概要设计 1、ADT定义 class Node //节点类 { public: char oper;//数据域，为简便起见，操作数用单个字符代替 Node *left; //左孩子 Node *right;//右孩子 int s;int t;//计算树的层数使用 Node() { left=right=NULL; oper=0; } Node(char op) { left=right=NULL; oper=op; } };

bool isOper(char op)//判断是否为运算符 void postOrder(Node *p) //先序遍历 void preOrder(Node *p) //后序遍历 void inOrder(Node *p)//中序遍历，同时输出不带冗余括号的中缀表达式 void post2tree(Node *&p,string str)//后缀表达式生成二叉树 void pre2tree(Node *&p, string str)//前缀表达式生成二叉树 void in2tree(Node *&p, string str)//中缀表达式转换成后缀表达式生成二叉树 void paint(Node *p)//打印树 void count(Node *p,int &height,int n)//求数的层数，以便与打印树 void freeTree(Node *&p) //递归删除树 int getOperOrder(char op)//返回运算符op所对应的优先级

2、主程序和各模块的调用 main() 输入的表达式存放于expression，flag用于标记输入哪种类型的表达式

为-1调用void pre2tree(Node *&p, string str)，将前缀表达式转化为二叉树 flag=? 为0调用void in2tree(Node *&p, string str)，将中缀表达式转化为二叉树 为1调用void post2tree(Node *&p,string str)，将后缀表达式转化为二

调用void paint(Node *p) 打印二叉树 调用void count(Node *p,int &height,int n)求数的高度

调用void preOrder(Node *p)输出前缀表达式

调用void inOrder(Node *p)输出中缀表达式

调用void postOrder(Node *p)输出前缀表达式 int main() { string expression; Node *tree;

cout<<"前缀表达式-1 中缀表达式0 后缀表达式1">flag; cout<<"请输入表达式:">expression;

if(flag==-1)//前缀表达式 pre2tree(tree,expression); else if(flag==1)//后缀表达式 post2tree(tree,expression); else //中缀表达式 in2tree(tree,expression); paint(tree); cout

三、详细设计 1、表达式转化为二叉树 （1）前缀表达式：从后往前扫描 ①遇到操作数，把它赋给新建立的二叉树结点，入栈； ②遇到运算符，把它赋给新建立的二叉树的节点。如果栈非空，从栈中弹出一个元素，把栈顶指针所指结点设为当前结点的左孩子，如果栈非空，再从栈中弹出一个元素，把栈顶指针所指结点设置为当前结点的右孩子，然后把当前节点压栈，最后一个元素就是二叉树的根结点。

（2）中缀表达式：把中缀表达式转换成后缀表达式，然后再生成二叉树。 ①定义一个运算符栈，并输入一个中缀表达式，然后从中缀表达式中自左至右依次读入各个字符。 ②如果读入操作数，直接输出到后缀表达式。 ③如果读入的是运算符，并且运算符栈为空，则将该运算符直接进栈；如果栈不为空， 则 比较该运算符和栈顶运算符的优先级。 ▪若该运算符高于栈顶运算符的优先级，则将该运算符直接进栈； •若该运算符低于或等于栈顶运算符的优先级，则将栈中高于或等于该运算符优先级的元 素依次出栈输出到后缀表达式中，然后再将该运算符进栈。 ④如果读入的是开括号“（”，则直接进栈；如果读入的是闭括号“）”，则一直出栈并输出到后缀表达式，直到遇到一个开括号“（”为止。开括号“（”和闭括号“）”均不输出到后缀表达式。 ⑤重复（2）（3）（4）步，直到中缀表达式结束，然后将栈中剩余的所有运算符依次出栈。

（3）后缀表达式：从前往后扫描 ①碰到操作数则把它赋给相应的新建立的二叉树结点，若栈为空则入栈， ②碰到运算符则把它赋给相应的新建立的二叉树结点，若当前结点的左孩子为空则设为其左孩子，左孩子为满则设为其右孩子。开始结点为根结点。

2、二叉树表达式转化为表达式 （1）前缀表达式：对二叉树表达式进行前序遍历。依次输出各结点。 （2）中缀表达式：对二叉树表达式进行中序遍历。 如果当前结点的左子树是运算符，且运算符优先级低于当前运算符，那么左边的表达式要先计算，需要加括号，否则直接输出左子树；如果当前结点的右子树是运算符，且运算符优先级不高于当前运算符，那么右边的表达式要先计算，需要加括号，否则直接输出右子树。 依次输出各结点。 （3）后缀表达式：对二叉树表达式进行后序遍历。依次输出各结点。

四、程序测试 五、源程序 #include #include #include #include #include using namespace std;

class Node//结点类 { public: char oper; Node *left; Node *right; int s;int t; Node() { left=right=NULL; oper=0; } Node(char op) { left=right=NULL; oper=op; } };

bool isOper(char op)//判断是否为运算符 { char oper[]={'(',')','+','-','*','/','^'}; for(int i=0;i{ if(op==oper[i]) { return true; } } return false; }

int getOperOrder(char op)//返回运算符op所对应的优先级 { switch(op){ case '(': return 1; case '+': case '-':return 2; case '*': case '/':return 3; case '^':return 4; default: return 0; } }

void freeTree(Node *&p) //递归删除树 { if(p->left!=NULL) freeTree(p->left); if(p->right!=NULL) freeTree(p->right); delete(p); }

void postOrder(Node *p) //先序遍历 { if(p) { postOrder(p->left); postOrder(p->right); cout

void preOrder(Node *p) //后序遍历 { if(p) { coutleft); preOrder(p->right); } }

void inOrder(Node *p)//中序遍历，同时输出不带冗余括号的中缀表达式 { if(p) { if(p->left) {//如果当前节点的左子树是运算符，且运算符优先级低于当前运算符， //那么左边的表达式要先计算，需要加括号 if(isOper(p->left->oper)&& getOperOrder(p->left->oper)oper)) { cout<<"("; inOrder(p->left); cout<<")"; } else//否则直接输出左子树 inOrder(p->left); }

coutright) { //如果当前节点的右子树是运算符，且运算符优先级不高于当前运算符， //那么右边的表达式要先计算，需要加括号 if(isOper(p->right->oper)&& getOperOrder(p->right->oper)<=getOperOrder(p->oper)) { cout<<"("; inOrder(p->right); cout<<")"; } else inOrder(p->right); } } }

void post2tree(Node *&p,string str)//后缀表达式生成二叉树 { stack nodeStack;//用于保存节点指针的栈 char temp; int i=0; temp=str[i++]; while(temp!='\0')