《表达式二叉树&amp#183;实验代码》由会员分享，可在线阅读，更多相关《表达式二叉树&amp#183;实验代码（6页珍藏版）》请在金锄头文库上搜索。
1、实验：表达式二叉树实验要求：建立表达式二叉树，并打印(可逆时针旋转 90度打印，也可尝试正向打印)以中缀表达式 a*b+(c-d)/e-f 为例，建立以-号为根的表达式二叉树。提示：若直接利用中缀表达式建立困难，可先将中缀表达式转化为后缀表达式(可 利用栈中的中缀到后缀转化程序实现中缀表达式到后缀表达式的转换，再根据后 缀表达式建立表达式二叉树，可参考栈中后缀表达式计算方法)。实验代码：#include #include #include #include #include using namespace std;class tnode;void buildexptree(const stri
2、ng &exp);void printexptree();int judgerank(char ch);bool isoperator(char ch);void test();void setxy(tnode *tn, int y);int X = 0;int Y = 0;int depth = 0;vectorvt;class tnode public:char nodeValue; int x, y;tnode *left; tnode *right;tnode()x = 0;y = 0;tnode(char &item, tnode *lptr = NULL, tnode *rptr
3、= NULL): nodeValue(item), left(lptr), right(rptr)x = 0;y = 0;tnode *myNode;bool cmp(tnode *t1, tnode *t2)if(t1-y != t2-y)return (t1-y) (t2-y);return (t1-x) x);class zpair/将 operator 和 rank 打包为一体,临时存储在 stk2 中public:char op;int rank;zpair()zpair(char _op, int _rank)op = _op;rank = _rank;int judgerank(
4、char ch)if(ch = () return -1;if(ch = + | ch = -) return 1;if(ch = * | ch = /) return 2;return 0;bool isoperator(char ch)if(ch = ( | ch = ) | ch = + | ch = - | ch = * | ch = /) return true;elsereturn false;void buildexptree(const string &exp)stackstk1;stackstk2;int i;int len = exp.length();char ch;zp
5、air tz;zpair ztop;for(i=0; ilen; i+) ch = expi;if(!isoperator(ch)/expi is an operand, so create a tnode using expi and pushto stk1tnode *ptr1 = new tnode(ch); stk1.push(ptr1);else tz.op = ch;tz.rank = judgerank(ch);if(stk2.empty() stk2.push(tz);else if(ch = () stk2.push(tz);else if(ch = ) ztop = stk
6、2.top(); while(ztop.op != ()tnode *ptr2 = stk1.top();stk1.pop();tnode *ptr3 = stk1.top();stk1.pop();tnode *ptr4 = new tnode(ztop.op, ptr3, ptr2); stk1.push(ptr4);stk2.pop();ztop = stk2.top();stk2.pop();elseztop = stk2.top();while(tz.rank = ztop.rank)tnode *ptr5 = stk1.top();stk1.pop();tnode *ptr6 =
7、stk1.top();stk1.pop();tnode *ptr7 = new tnode(ztop.op, ptr6, ptr5);stk1.push(ptr7);stk2.pop();if(stk2.empty() break;else ztop = stk2.top();stk2.push(tz);while(!stk2.empty()tnode *ptr8 = stk1.top();stk1.pop();tnode *ptr9 = stk1.top();stk1.pop();tnode *ptr10 = new tnode(stk2.top().op, ptr9, ptr8);stk1
8、.push(ptr10);stk2.pop();myNode = stk1.top();int main()freopen(chris.txt,r,stdin);string exp;cout Please input an expression: exp;buildexptree(exp);cout The expression tree is: endl;printexptree();return 0;void test()/测试函数cout testing. endl;void printexptree() setxy(myNode, Y); sort(vt.begin(),vt.end
9、(),cmp);int tmpY = 1;int tmpX = 0;for(int i=0; iy tmpY) cout endl; tmpX = 0; tmpY-;cout x - tmpX - 1 , ) nodeValue; tmpX = vti-x; cout left, y-1); tn-x = +X;tn-y = y; vt.push_back(tn);/* cout nodeValue= nodeValue x= x y= y right,y-1); depth+;实验截图：实验分析：通过类tnode构造了一个表达式二叉树，除了节点值nodeValue,左分支left和 右分支right, 还引入了 x, y作为标定的坐标，打印时使用。首先完成infix2postfix，这其中使用了 stkl, stk2两个栈分别存储子树和zpair量，zpair是将operator与其优先级打包的一个整体，然后 通过比较优先级，调整stk1中的元素，构造了后缀表达式。打印过程中，先调用setxy（）方法来设定每个节点的坐标值，使用的是中序遍历，同时声 明了存储各个节点的向量vt,将所有节点压入vt后先按y再按x排序，然后按格式输出表 达式二叉树。
