下载文档原格式
浙江大学城市学院实验报告课程名称python高级程序设计实验项目名称实验五二叉树的应用----表达式求值实验成绩指导老师（签名）日期一.实验目的和要求1、掌握二叉树的链式存储结构；2、掌握在二叉链表上的二叉树的基本操作；3、掌握二叉树的简单应用----表达式树的操作。
二.实验内容1、在实验四中，已经实现了对一个中缀表达式可以用栈转换成后缀表达式，并可对后缀表达式进行求值计算的方法。
另一种思路是可以利用二叉树建立表达式树，通过对该表达式树进行求值计算，本实验实现：输入一个中缀表达式，建立该表达式的二叉树，然后对该二叉树进行表达式值的计算。
如一个中缀达式(6+2)*5 的二叉树表示为如下所示时，该二叉树的后序遍历62+5*正好就是后缀表达式。
设一般数学表达式的运算符包括+、-、*、/ 四种，当然允许（），且（）优先级高。
为方便实现，设定输入的表达式只允许个位整数。
要求设计一个完整的程序，对输入的一个日常的中缀表达式，实现以下功能：⏹建立对应的二叉树⏹输出该二叉树的前序序列、中序序列、后序序列⏹求该二叉树的高度⏹求该二叉树的结点总数⏹求该二叉树的叶子结点数⏹计算该二叉树的表达式值分析：（1）表达式树的构建方法：●构建表达式树的方法之一：直接根据输入的中缀表达式构建对于任意一个算术中缀表达式，都可用二叉树来表示。
表达式对应的二叉树创建后，利用二叉树的遍历等操作，很容易实现二叉树的求值运算。
因此问题的关键就是如何创建表达式树。
对于一个中缀表达式来说，其表达式对应的表达式树中叶子结点均为操作数，分支结点均为运算符。
由于创建的表达式树需要准确的表达运算次序，因此，在扫描表达式创建表达式树的过程中，当遇到运算符时不能直接创建结点，而应将其与前面的运算符进行优先级比较，根据比较结果进行处理。
这种处理方式在实验四中以采用过，可以借助一个运算符栈，来暂存已经扫描到的还未处理的运算符。
根据表达式树与表达式对应关系的递归定义，每两个操作数和一个运算符就可以建立一棵表达式二叉树，而该二叉树又可以作为另一个运算符结点的一棵子树。
软考初级程序员真题及答案1.在Windows资源管理中，如果选中的某个文件，再按Delete 键可以将该文件删除，但需要时还能将该文件恢复。
若用户同时按下Delete和（）组合键时，则可以删除此文件且无法从回收站恢复。
A.CtrlB.ShiftC.AltD.Alt 和Ctrl【答案】B2.计算机软件有系统软件和应用软件，下列（）属于应用软件。
本资料摘自文得学习网，更多计算机等级考试题库视频，上文得学习网查看。
A.LinuxB.UnixC.Windows 7D.Internet Explorer【答案】D固定题干3.某公司2016年10月员工工资表如下所示。
若要计算员工的实发工资，可先在J3单元格中输入（1 ）,再向垂直方向拖动填充柄至J12单元格，则可自动算出这些员工的实发工资。
若要将缺勤和全勤的人数统计分别显示在B13和D13单元格中，则可B13和D13 中分别填写（2 ）o1.( 1 )A.=SUM(D$3:F$3)+(H$3:I$3)B.=SUM(D$3:F$3)+(H$3:I$3)C.=SUM(D3:F3)-SUM(H3:I3)D.=SUM(D3:F3)+SUM(H3:I3)【答案】C2.( 2 )A.=COUNT(E3 正12,xO)和=COUNT(E3 正12 广300)B.=COUNT(E3:E12, ">=0")和=COUNT(E3:E12, H =300")C.=COUNTIF(E3:E12,>=0)和二COUNTIF(E3 正12 广300)D.=COUNTIF(E3:E12, ”=0“)和=COUNTIF(E3:E12, ” =300”)【答案】D4,统一资源地址（URL）/index.html 中的http 和index.html分别表示（）。
A.域名、请求查看的文档名B.所使用的协议、访问的主机C.访问的主机、请求查看的文档名D.所使用的协议、请求查看的文档名【答案】D5.以下关于CPU的叙述中，正确的是（）A.CPU中的运算单元、控制单元和寄存器组通过系统总线连接起来B.在CPU中，获取指令并进行分析是控制单元的任务C.执行并行计算任务的CPU必须是多核的D.单核CPU不支持多任务操作系统而多核CPU支持【答案】B6.在存储体系中，位于主存与CPU之间的高速缓存(Cache)用于存放主存中部分信息的副本，主存地址与Cache地址之间的转换工作()。
张东1145105494简介：1、算法+数据结构=程序2、数据结构3、数据、数据元素（基本单位）、数据项（最小单位）4、数据结构在计算机中的映像是存储结构；数据元素在计算机中的映像是结点；数据项在计算机中的映像是数据域；逻辑结构在计算机中的映像是关系。
5、四种存储方式6、抽象数据类型1）按不同特性分类●原子类型●固定聚合类型●可变聚合类型2）基本操作●init 构造●destroy 销毁●get 返回●put 改变●isasc 升序●isdesc 降序●Max 最大●min 最小7、时间复杂度技巧1）对于循环程序（for），最大执行次数即为for的乘积。
简言之，程序有多少for出现，就是n的多少次方2）对于顺序结构，可用“求和取最大值“法则3）对于循环程序（while），一般结果是O(log M N)4）若是一般的赋值语句，时间复杂度必为O(1)5）对于选择结构的程序，一般时间复杂度为O(1)加：自加自减++ ——x=2；y=x++;y=++x;第二章线性表1、表长相当于元素个数2、线性表一般下标是1—n，故当n=0时，表示线性表为空表3、list 表示线性表elem 元素length 表示求长度（线性表）locate 定位（位置）insert 插入（元素之前）delete 删除void 空类型（写程序必写）顺序结构（链表相反）优势：随机存取劣势：在做插入或删除时需要移动大量的元素malloc 分配一个连续空间realloc 将已分配的空间进行重新分配顺序表插入时所需移动的元素次数期望值是n/2删除时所需移动的元素次数期望值是（n-1）/2删除：模板语句：q=&(L.elem[i-1]) 表示顺序表中插入元素或者删除元素的地址加：逻辑运算符：！非&&与（一假即假）||或（一真即真）逻辑值：真（1）假（0）比较运算符：< >= <= == !=若在if或者while后面的括号中出现逻辑表达式或者比较表达式，那么结果只能为真或假。
二叉树计算表达式计算表达式是计算机科学中常见的任务，而二叉树是一种常用的数据结构，用于表示表达式。
本文将介绍二叉树如何表示和计算表达式。
一、二叉树表示表达式二叉树是由节点和边组成的树状结构。
每个节点都包含一个值和两个指向左右子节点的指针。
二叉树可以用来表示数学表达式。
例如，下面是一个包含加、减、乘、除的表达式：```5 + 3 *6 / 2 - 4```将表达式转化为二叉树表示，根节点为`-`，其左子树是`+`，右子树是`4`。
`+`节点的左子树为`5`，右子树为`/`。
`/`节点的左子树为`*`，右子树为`2`。
`*`节点的左子树为`3`，右子树为`6`。
```-/ \+ 4/ \5 // \* 2/ \3 6```每个节点的值表示该节点的操作符或操作数。
叶子节点是操作数，内部节点是操作符。
二、计算二叉树表达式计算表达式需要递归地对二叉树进行遍历。
从根节点开始，如果是操作符节点，就对其左右子节点进行递归。
如果是操作数节点，就返回该节点的值。
等到递归完成后，就可以根据操作符节点的值和左右子节点的值对表达式进行计算了。
对于上面的表达式二叉树，计算的过程如下。
首先计算根节点的左右子节点，即`+`节点和`4`节点的值。
`+`节点还需要计算其左右子节点`5`和`/`节点的值。
`/`节点又需要计算其左右子节点`*`和`2`的值。
`*`节点需要计算其左右子节点`3`和`6`的值。
归纳起来，计算的顺序是从下到上，从左到右。
```-/ \+ 4/ \5 // \* 2/ \3 6```按照计算顺序求值：1. 计算`3 * 6`，得到18。
2. 计算`6 / 2`，得到3。
3. 计算`3 / 3`，得到1。
4. 计算`5 + 1`，得到6。
5. 计算`6 - 4`，得到2。
因此，表达式`5 + 3 * 6 / 2 - 4`的值是2。
三、扩展上面的例子说明了如何将表达式转为二叉树，并计算表达式的值。
但实际中会有更复杂的表达式，如函数调用、变量引用等。
完全二叉树的总结点数公式完全二叉树是一种特殊的二叉树结构，它的每个节点都有两个子节点，除了最后一层的叶子节点外，其他层的节点都是满的。
在完全二叉树中，叶子节点只会出现在最后一层或者倒数第二层，并且最后一层的叶子节点都靠左排列。
在这篇文章中，我们将探讨完全二叉树的总结点数公式以及相关的性质。
完全二叉树的总结点数公式是一个重要的数学公式，它可以帮助我们计算完全二叉树中节点的数量。
这个公式的表达式如下：总结点数 = 2的h次方 - 1其中，h代表完全二叉树的高度。
这个公式的推导过程是基于完全二叉树的性质而得出的。
在完全二叉树中，每一层的节点数都是满的，除了最后一层。
因此，在计算总结点数时，我们只需要计算除了最后一层外的节点数量，然后再加上最后一层的节点数即可。
我们来看完全二叉树的第一层。
由于完全二叉树的定义，第一层只有一个节点，即根节点。
因此，第一层的节点数为1。
接下来，我们来看完全二叉树的第二层。
根据完全二叉树的定义，第二层的节点数等于第一层节点数的两倍，即2。
继续往下，我们可以得到第三层的节点数为4，第四层的节点数为8，以此类推。
可以观察到，每一层的节点数都是2的次方。
因此，我们可以用2的h次方来表示每一层的节点数。
接下来，我们需要计算除了最后一层之外的节点数。
在完全二叉树中，除了最后一层的节点数是满的，其他层的节点数都是满的。
如果完全二叉树的高度为h，那么除了最后一层之外的节点数可以用以下公式表示：除最后一层之外的节点数 = 2的(h-1)次方 - 1接下来，我们需要计算最后一层的节点数。
根据完全二叉树的定义，最后一层的节点数是小于或等于前面各层节点数的两倍。
因此，最后一层的节点数可以用以下公式表示：最后一层的节点数 = 2的(h-1)次方或者 2的h次方 - 2的(h-1)次方我们将除了最后一层之外的节点数和最后一层的节点数相加，即可得到完全二叉树的总结点数。
将上述公式代入，我们可以得到完全二叉树的总结点数公式：总结点数 = 2的(h-1)次方 - 1 + 2的h次方 - 2的(h-1)次方简化上述公式，我们可以得到：总结点数 = 2的h次方 - 1这就是完全二叉树的总结点数公式。
《数据结构》实验报告题目: 树和二叉树一、用二叉树来表示代数表达式（一）需求分析输入一个正确的代数表达式, 包括数字和用字母表示的数, 运算符号+ - * / ^ =及括号。
系统根据输入的表达式建立二叉树, 按照先括号里面的后括号外面的, 先乘后除的原则, 每个节点里放一个数字或一个字母或一个操作符, 括号不放在节点里。
分别先序遍历, 中序遍历, 后序遍历此二叉树, 并输出表达式的前缀式, 中缀式和后缀式。
（二）系统设计1.本程序中用到的所有抽象数据类型的定义；typedef struct BiNode //二叉树的存储类型{char s[20];struct BiNode *lchild,*rchild;}BiTNode,*BiTree;2.主程序的流程以及各程序模块之间的层次调用关系, 函数的调用关系图:3. 列出各个功能模块的主要功能及输入输出参数void push(char cc)初始条件: 输入表达式中的某个符号操作结果: 将输入的字符存入buf数组中去BiTree Create_RTree()初始条件: 给出二叉树的定义表达式操作结果：构造二叉树的右子树, 即存储表达式等号右侧的字符组BiTree Create_RootTree()初始条件: 给出二叉树的定义表达式操作结果：构造存储输入表达式的二叉树, 其中左子树存储‘X’, 根节点存储‘：=’void PreOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：先序遍历T, 对每个节点调用函数Visit一次且仅一次void InOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：中序遍历T, 对每个节点调用函数Visit一次且仅一次void PostOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：后序遍历T, 对每个节点调用函数Visit一次且仅一次int main()主函数, 调用各方法, 操作成功后返回0（三）调试分析调试过程中还是出现了一些拼写错误, 经检查后都能及时修正。
最早提出遍历问题的是对存储在计算机中的表达式求值。
例如：(a+b ×(c-d))-e/f 。
表达式用树形来表示，如图8-11-1所示。
运算符在树中放在非终端结点的位置上，操作数放在叶子结点处。
当我们对此二叉树进行先序、中序和后序遍历后，便可得到表达式的前缀、中缀和后缀书写形式：前缀：-+a*b-cd/ef中缀：a+b*c-d-e/f 后缀：abcd-*+ef/-其中，中缀形式是算术表达式的通常形式，只是没有括号。
在计算机内，使用后缀表达式易于求值。
例1 输入一个算术表达式，判断该表达式是否合法，若不合法，给出错误信息；若合法，则输出合法表达式的表达式树。
【算法分析】表达式不合法有三种情况：①左右括号不匹配；②变量名不合法；③运算符两旁无参与运算的变量或数。
分析表达式树可以看到：表达式的根结点及其子树的根结点为运算符，其在树中的顺序是按运算的先后顺序从后到前，表达树的叶子为参与运算的变量或数。
表达式树如图8-11-2处理时，首先找到运算级别最低的运算符“+”作为根结点，继而确定该根结点的左、右子树结点在表达式串中的范围为a 和(b-c)/d ，再在对应的范围内寻找运算级别最低的运算符作为子树的根结点，直到范围内无运算符，则剩余的变量或数为表达式树的叶子。
【算法步骤】① 设数组ex 存放表达式串的各字符，lt 、rt 作为结点的左右指针，变量left 、right 用于存放每次取字符范围的左、右界。
② 设置左界初值为1；右界初值为串长度。
③ 判断左右括号是否匹配，不匹配则认为输入有错误。
④ 在表达式的左右界范围内寻找运算级别最低的运算符，同时判断运算符两旁有否参与运算的变量或数。
若无，则输入表达式不合法；若有，作为当前子树的根结点，设置左子树指针及其左右界值，设置右子树指针及其左右界值。
⑤ 若表达式在左右界范围内无运算符，则为叶子结点，判断变量名或数是否合法。
⑥ 转④，直到表达式字符取完为止。
c语言基于二叉树的表达式求值算法C语言中，基于二叉树的表达式求值算法主要包括两部分：中缀表达式转换为后缀表达式和后缀表达式求值。
1.中缀表达式转换为后缀表达式中缀表达式是我们常见的数学表达方式，例如3 + 4 * 2 - 5。
为了方便计算机求值，我们需要将中缀表达式转换为后缀表达式，也叫做逆波兰表达式。
转换的过程使用栈数据结构来实现。
具体算法如下：1.定义一个栈和一个结果字符串，栈用于存储操作符，结果字符串用于保存后缀表达式。
2.从左到右遍历中缀表达式的每一个字符。
3.如果当前字符是数字，直接将其加入结果字符串。
4.如果当前字符是左括号"("，将其入栈。
5.如果当前字符是右括号")"，则依次将栈顶的操作符弹出并加入结果字符串，直到遇到左括号为止，同时将左括号从栈中弹出。
6.如果当前字符是操作符，需要将栈中优先级比当前操作符高或者相等的操作符弹出并加入结果字符串，然后将当前操作符入栈。
7.遍历完所有字符后，将栈中剩余的操作符依次弹出并加入结果字符串。
8.最终结果字符串就是后缀表达式。
例如，对于中缀表达式3 + 4 * 2 - 5，转换为后缀表达式为3 4 2 * + 5 -2.后缀表达式求值后缀表达式求值算法使用栈数据结构来实现。
具体算法如下：1.定义一个栈，用于存储操作数。
2.从左到右遍历后缀表达式的每一个字符。
3.如果当前字符是数字，则将其转换为对应的整数并入栈。
4.如果当前字符是操作符，则从栈中弹出两个操作数，先弹出的作为右操作数，后弹出的作为左操作数，根据操作符进行运算，得到结果后入栈。
5.遍历完所有字符后，栈顶的数字即为最终的结果。
例如，对于后缀表达式3 4 2 * + 5 -，求值的过程如下：1.入栈3。
2.入栈4。
3.入栈2。
4.弹出2和4，计算4 * 2 = 8，将8入栈。
5.弹出8和3，计算3 + 8 = 11，将11入栈。
6.入栈5。
7.弹出5和11，计算11 - 5 = 6，得到最终结果。
利⽤⼆叉树求表达式的值利⽤⼆叉树求表达式的值，⾸先要注意表达式中先乘除后加减的运算顺序，所以在建⽴树的过程中，就要将加减尽量作为根节点，最后⼀个加减号作为根节点。
建完树之后是运算过程，采⽤树的后序遍历来运算。
⼆叉树的节点结构，其中值的类型⽤char型struct node{char data;node* left;node* right;};node *CRTree(char s[],int begin,int end){node *p;int k,plus=0,posi;if (begin==end) //只有⼀个字符，构造的是⼀个叶⼦节点{p=(node *)malloc(sizeof(node)); //分配存储空间p->data=s[begin]; //值为s[begin]p->left=NULL;p->right=NULL;return p;}//以下为begin!=end的情况for (k=begin; k<=end; k++)if (s[k]=='+' || s[k]=='-'){plus++;posi=k; //最后⼀个+或-的位置}if (plus==0) //没有+或-的情况(因为若有+、-，前⾯必会执⾏plus++)for (k=begin; k<=end; k++)if (s[k]=='*' || s[k]=='/'){plus++;posi=k;}//以上的处理考虑了优先将+、-放到⼆叉树较⾼的层次上//由于将来计算时，运⽤的是后序遍历的思路//处于较低层的乘除会优先运算//从⽽体现了“先乘除后加减”的运算法则//创建⼀个分⽀节点，⽤检测到的运算符作为节点值if (plus!=0){p=(node *)malloc(sizeof(node));p->data=s[posi]; //节点值是s[posi]p->left=CRTree(s,begin,posi-1); //左⼦树由s[begin]⾄s[posi-1]构成p->right=CRTree(s,posi+1,end); //右⼦树由s[posi+1]到s[end]构成return p;}else//若没有任何运算符，返回NULLreturn NULL;}下⾯是运算过程double Comp(node *b){double v1,v2;if (b==NULL)return0;if (b->left==NULL && b->right==NULL) //叶⼦节点，应该是⼀个数字字符（本项⽬未考虑⾮法表达式）return b->data-'0'; //叶⼦节点直接返回节点值，结点中保存的数字⽤的是字符形式，所以要-'0'v1=Comp(b->left); //先计算左⼦树v2=Comp(b->right); //再计算右⼦树switch(b->data) //将左、右⼦树运算的结果再进⾏运算，运⽤的是后序遍历的思路{case'+':return v1+v2;case'-':return v1-v2;case'*':return v1*v2;case'/':if (v2!=0)return v1/v2;elseabort();}}最后要记得将新建的⼆叉树销毁void DestroyBTNode(node *&b) //销毁⼆叉树{if (b!=NULL){DestroyBTNode(b->left);DestroyBTNode(b->right);free(b);}}。
数据结构程序报告（3）2011.3.292. 需求分析：（1）功能：表达式可以用二叉树表示，对于简单的四则运算，请实现以下功能【1】对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一棵表达式二叉树，并且图示出来（图形的形式）。
【2】对于构造好的内部表达式二叉树，按照用户的要求输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括）或后缀表达式（不带括号）。
提示：所谓中缀表达式中的冗余括号，就是去掉括号后不影响表达式的计算顺序。
例如：“（c+b）+a”中的括号是冗余的，可以表示成不冗余的“c+b+a”。
（2）输入输出要求：请输入字符串表达式：树形二叉树（图形显示）中缀表达式为：前缀表达式为：后缀表达式为：3.概要设计：（算法）分成两部分完成：【1】前缀、中缀、后缀表达式->二叉树表达式前缀表达式->二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，地址压栈；（b）碰到操作符则把其值赋给相应的新申请的二叉树，并从栈中弹出两个地址，分别作为其右指针和左指针，然后再把其地址压栈，最后一个地址即为二叉树的根结点地址。
中缀表达式->二叉树表达式：把中缀表达式转换成后缀表达式，然后再建立二叉树。
后缀表达式->二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，若栈为空则地址压栈，若非空则取栈顶元素，若栈顶元素的左孩子为空则当前结点设为其左孩子，左孩子为满则设为其右孩子再压栈；（b）碰到操作数则把其值赋给相应的新申请的二叉树结点，取栈顶元素，若栈顶元素的左孩子为空则设为其左孩子，左孩子为满则设为其右孩子开始那个元素地址为根结点地址，开始时用变量root保存。
【1】二叉树表达式->前缀、中缀、后缀表达式二叉树表达式->前缀表达式：对二叉树表达式进行前序遍历。
二叉树表达式->中缀表达式：对二叉树表达式进行中序遍历，若结点操作符的优先级高于其左或右子树，在打印相应的子树之前先打印开括号，在打印相应的子树最后在打印一个闭括号。
二叉树表达式->后缀表达式：对二叉树表达式进行后序遍历。
建立表达式树就是建立树中的每一个结点，将每一个结点链接起来就是整棵树。
而在建立深度低的结点时要将其左右指针指向之前建立的深度比它高一级的结点(如’*’要指向’2’和’3’，而’+’又要指向’*’)。
这样我们可以用栈来存放每次建立的结点，按照优先级(表达式为中缀型)或顺序扫描表达式(表达式为波兰式与逆波兰式)建立每一个结点。
建立结点的顺序即为表达式求值的顺序。
如果扫描到操作数则直接新建一个左右指针为空的结点，并压入结点栈中(存放结点指针)。
遇到运算符时首先新建一个结点，然后从栈中依次弹出两个结点，并让新建立的结点的左右指针域指向它们。
当所有结点建立完毕时，如果表达式没有错误(这里假设输入表达式正确)，这时栈中应该只剩下一个结点，它就是所建立的表达式的根结点。
4. 详细设计：（具体方法）首先创建一个节点类TNode：包含操作符oper、左孩子left、右孩子right，isOper （）判断是否为操作符，getOperOrder（）返回运算符op所对应的优先级，freeTree（）程序结束销毁二叉树，postOrder（）先序遍历，preOrder（）后序遍历，inOrder（）中序遍历，ExpTree1（）后缀表达式生成二叉树，ExpTree3（）前缀表达式生成二叉树，ExpTree2（）中后缀表达式生成二叉树，count（）求值函数，paint（）输出函数附程序：#include <iostream>#include <stack>#include <queue>#include <string>#include<math.h>using namespace std;class TNode//节点类{ public:char oper;TNode *left;TNode *right;int s；int t；TNode(){ left=right=NULL;oper=0;}TNode(char op){ left=right=NULL;oper=op;}};bool isOper(char op)//判断是否为运算符{char oper[]={'(',')','+','-','*','/','^'};for(int i=0;i<sizeof(oper);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(TNode *&p)//释放树{ if(p->left!=NULL)freeTree(p->left);if(p->right!=NULL)freeTree(p->right);delete(p);cout<<"Memory free "; }void postOrder(TNode *p) //先序遍历{ if(p){ postOrder(p->left);postOrder(p->right);cout<<p->oper;} }void preOrder(TNode *p) //后序遍历{ if(p){ cout<<p->oper;preOrder(p->left);preOrder(p->right);} }void inOrder(TNode *p)//中序遍历{ if(p){ if(p->left){ if(isOper(p->left->oper)&& getOperOrder(p->left->oper)<getOperOrder(p->oper)){ cout<<"(";inOrder(p->left);cout<<")";}else{inOrder(p->left);} }cout<<p->oper;if(p->right){ if(isOper(p->right->oper)&& getOperOrder(p->right->oper)<=getOperOrder(p->oper)){ cout<<"(";inOrder(p->right);cout<<")";}else{inOrder(p->right);} } } }void ExpTree1(TNode *&p,string str)//后缀表达式生成二叉树{stack <TNode*> nodeStack;char temp;int i=0;temp=str[i++];while(temp!='\0'){ if(temp!='\0'&&!isOper(temp))//不是运算符，则进栈{ p=new TNode(temp);//以temp为结点值构造二叉树结点nodeStack.push(p);temp=str[i++];}else{ p=new TNode(temp);if(nodeStack.size()){ p->right=nodeStack.top();//若非空则弹栈并设为结点的右孩子nodeStack.pop(); }if(nodeStack.size()){ p->left=nodeStack.top();//若非空则弹栈并设为结点的左孩子nodeStack.pop(); }nodeStack.push(p);temp=str[i++];} } }void ExpTree3(TNode *&p, string str)//前缀表达式生成二叉树{ stack <TNode*> nodeStack;char temp;int i=str.size()-1;temp=str[i--];while(temp!='\0'){ if(temp!='\0'&&!isOper(temp)){ p=new TNode(temp);//以temp为内容来建立新的结点nodeStack.push(p);temp=str[i--];}else{ p=new TNode(temp);if(nodeStack.size())//若栈顶指针所指结点左孩子为空{ p->left=nodeStack.top(); //则当前结点设置成其左孩子nodeStack.pop();} if(nodeStack.size())//若栈顶指针所指结点右孩子为空{ p->right=nodeStack.top();//则当前结点设置成其右孩子nodeStack.pop();//栈顶元素左右孩子指针设置完毕弹出}nodeStack.push(p);temp=str[i--];} } }void ExpTree2(TNode *&p, string str)//中缀表达式转换成后缀表达式生成二叉树{ stack<char> a;char temp;string Postfixexp="";int i=0;temp=str[i++];while(temp!='\0'){ if(!isOper(temp)){ Postfixexp+=temp;temp=str[i++];}else if(temp=='(')//进栈{ a.push(temp);temp=str[i++];}else if(temp==')'){while(a.top()!='(')//脱括号{ Postfixexp+=a.top();a.pop();//在碰到开括号和栈为空前反复弹出栈中元素}a.pop();temp=str[i++];}else if(temp=='+'||temp=='-'||temp=='*'||temp=='/')//出栈{ while(!a.empty()&&a.top()!='('&&getOperOrder(a.top())>=getOperOrder(temp))//若栈非空栈顶不是左括号且栈顶元素优先级不低于输入运算符时，//将栈顶元素弹出到后缀表达式中，并且str下标加1{ Postfixexp+=a.top();a.pop(); }a.push(temp);temp=str[i++];} }while(!a.empty()){ Postfixexp+=a.top();a.pop();}ExpTree1(p,Postfixexp); }void count(TNode *p,int &height,int n)//求值函数{ if(p->left==NULL&&p->right==NULL){ if(n>height)height=n;}if(p->left!=NULL)count(p->left,height,n+1);if(p->right!=NULL)count(p->right,height,n+1); }void paint(TNode *p)//输出函数{ int height=0;int h=0;int i;using std::queue;queue<TNode*> aQueue;count(p,height,1);TNode *pointer=p;TNode *lastpointer;if(pointer){ pointer->s=1;pointer->t=1;aQueue.push(pointer); }while(!aQueue.empty()){ lastpointer=pointer;pointer=aQueue.front();aQueue.pop();if(pointer->s>h){cout<<endl;h=pointer->s;}if(pointer->t==1){for(i=0;i<pow(2,height-pointer->s)-1;i++) cout<<" ";}else if(lastpointer->s!=pointer->s){for(i=0;i<(pointer->t-1)*(pow(2,height-pointer->s+1)-1)+(pointer->t-1)-1+pow(2, height-pointer->s);i++)cout<<" "; }else{ for(i=0;i<(pointer->t-lastpointer->t)*(pow(2,height-pointer->s+1)-1)+(pointer->t -lastpointer->t)-1;i++)cout<<" "; }cout<<pointer->oper;if(pointer->left!=NULL){pointer->left->s=pointer->s+1;pointer->left->t=pointer->t*2-1;aQueue.push(pointer->left);}if(pointer->right!=NULL){pointer->right->s=pointer->s+1;pointer->right->t=pointer->t*2;aQueue.push(pointer->right);} } }int main(){ string expression;TNode *tree;cout<<endl<<"请输入字符串表达式:";cin>>expression;if(isOper(expression[0]))ExpTree3(tree,expression);else if(isOper(expression[1])) ExpTree2(tree,expression);elseExpTree1(tree,expression);paint(tree);cout<<endl;cout<<"中缀表达式为:";inOrder(tree);cout<<endl;cout<<"前缀表达式为:";preOrder(tree);cout<<endl;cout<<"后缀表达式为:";postOrder(tree);cout<<endl;freeTree(tree);cout<<endl;system("pause");return 0; }5．测试数据：（1）请输入字符串表达式：-+1*234-+ 41*2 3中缀表达式为：1+2*3-4前缀表达式为：-+1*234后缀表达式为：123*+4-memory free memory free memory free memory free memory free 请按任意键继续………………………..（2）请输入字符串表达式：1+2*3-4-+ 41*2 3中缀表达式为：1+2*3-4前缀表达式为：-+1*234后缀表达式为：123*+4-memory free memory free memory free memory free memory free 请按任意键继续………………………..（3）请输入字符串表达式：123*+4--+ 41*2 3中缀表达式为：1+2*3-4前缀表达式为：-+1*234后缀表达式为：123*+4-memory free memory free memory free memory free memory free请按任意键继续………………………..测试截图：6．总结：程序调试中的问题及解决方法：前缀表达式建树，通过入栈出栈操作求出前缀表达式的逆序，针对得到的逆序表达式通过后缀表达式建立二叉树的方法，遇到操作数则入栈，遇到操作符则从栈中弹出两个操作数构建一棵小的二叉树，然后将小树的根节点入栈以便于下次操作。
