二叉表达式树

////////////////////////////// #include<iostream.h> #include<string.h> /*//////////////////////////// 全局变量定义 ///////////////////////////*/ char op[81];//保存原始字符串 int len=0;//记录经整理后的字符串的个数 int opw[81];//保存优先级 char a[81]; // 保存去掉括号后的表达式 const int max=81;//允许输入的最长字符串 ////////////////////////////////////// ///栈类定义 /// //////////////////////////////////////// template<class T> class stack { private: int top; int MaxSize; T*stak; public: stack() { top=-1; MaxSize=20; stak=new T[MaxSize]; } ~stack() { delete[]stak; } bool IsFull() { if(top==MaxSize) return true; else return false; } bool IsEmpty() { if(top==-1) return true; else return false; } void Push(T a) { if(!IsFull()) stak[++top]=a; else cout<<"overflow!"<<endl; } T Pop( ) { T a; if(!IsEmpty()) { a=stak[top--]; return a; } else return 0; } T GetTop() { if(!IsEmpty()) return stak[top]; else return 0; } }; /////////////////////////////////////////// //判断字符是否为运算符 /////////////////////////////////////////////// bool IsOper(char a ) { switch(a) { case'+': case'-': case'*': case'/': return true; break; default: return false; } } //////////////////////////////////////// //分析优先级 //template<class T> ////////////////////////////////// void analysis(char exp[]) { int w=0;//权值 int i=0; while(exp[i]) { switch(exp[i]) { case'(': w+=2; break; case')': w-=2; break; case'+': case'-': op[len]=exp[i]; opw[len]=w+1; len++; break; case'*': case'/': op[len]=exp[i]; opw[len]=w+2; len++; break; default: op[len]=exp[i]; opw[len]=0; len++; break; } i++; } } /////////////////////////////////////// stack<char>s1;//保存运算符和操作数 stack<int>s2;//保存优先级 ////////////////////////////////// //将中缀表达式变成后缀表达式，后缀表达式保存在数组a【】中 ///////////////////////////////// void MidTopost() { int i=0; int id=0; for(i=0;i<len;i++) { if(opw[i]==0) a[id++]=op[i]; else { if(s1.IsEmpty()) { s1.Push(op[i]); s2.Push(opw[i]); } else { int k; k=s2.GetTop(); if(k<opw[i]) { s1.Push(op[i]); s2.Push(opw[i]); } else { a[id++]=s1.Pop(); s2.Pop(); s1.Push(op[i]); s2.Push(opw[i]); } }//end of the second else }//end of the first else }//end of for while(!s1.IsEmpty()) { a[id++]=s1.Pop(); s2.Pop(); } } ///////////////////////////////////// //////////////////////////////////// //template<class T> struct TreeNode { char data; int depth; TreeNode*left; TreeNode*right; }*temp,*root,*queue[max],*rootnode[max];//变量 //////////////////////////// /// ////////////////////////////// //格式控制输出 递归实现 void print(TreeNode* a) { if(a==NULL) return; TreeNode* b=a->right; print(b); int i=2*a->depth;; while(i>0) { cout<<" "; i--; } len--; cout<<a->data<<endl; b=a->left; print(b); return; } /*///////////////////////////////////////// 改变树的每一层上字符的深度 ////////////////////////////////////////*/ void ChangeDepth(TreeNode*p) {//用循环队列实现逐层遍历 int rear=0; int front=0; queue[++rear]=p;//p为头结点 while(front!=rear) { front=(front+1)%max; if(queue[front]==root) queue[front]->depth=0;//树的根，深度为0 else queue[front]->depth++; if(queue[front]->left!=NULL)////将左孩子加入队列 { rear=(rear+1)%max; queue[rear]=queue[front]->left; } if(queue[front]->right!=NULL)//将右孩子加入队列 { rear=(rear+1)%max; queue[rear]=queue[front]->right; } } } ///////////////////////////////////////////////////////////////////// void main() { int i=0; char exp[81]; cout<<"============================"<<endl; cout<<"请输入一个表达式"<<endl; cout<<"============================"<<endl; cin.getline(exp,81);//获得一字符串 analysis(exp);//除掉中缀表达式中的括号，并判断运算符的优先级 MidTopost();//中缀变后缀 ///////////////////////////////////////// //构建一棵二叉树，用一结点栈rootnode[]保存根节点 //同时改变各层的深度depth的值 ////////////////// int top=-1; for(i=0;i<len;i++) { if(!IsOper(a[i])) { temp=new TreeNode; temp->data=a[i]; temp->depth=0; temp->left=NULL; temp->right=NULL; root=temp; top++; rootnode[top]=root; } else { temp=new TreeNode; temp->data=a[i]; temp->depth=0; root=temp; int count=0; while(count<2&&top!=-1) { if(count==0) { root->right=rootnode[top]; top--; } if(count==1) { root->left=rootnode[top]; top--; } count++; }//end of while top++; rootnode[top]=root; ChangeDepth(root); }//end of else }//end for //finish creating a tree// ///////////////////////////// //输出 cout<<"============================="<<endl; print(root);//打印输出 cout<<"=============================="<<endl; /////////////////////////////////////////// }