数据结构实验二叉树.docx

1、数据结构实验二叉树实验六：二叉树及其应用一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。二、问题描述首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。如算术表达式：a+b*(c-d)-e/f三、实验要求如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实

2、验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C+ 程序集成环境五、实验步骤1、根据二叉树的各种存储结构建立二叉树；2、设计求叶子结点个数算法和树的深度算法；3、根据表达式建立相应的二叉树，生成表达式树的模块；4、根据表达式树，求出表达式值，生成求值模块；5、程序运行效果，测试数据分析算法。六、测试数据1、输入数据：*（+）3 正确结果：2、输入数据：(1+2)*3+(5+6*7); 正确输出：56七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析：1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的

3、操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。例如有如下的中缀表达式：a+b-c转换成后缀表达式为：ab+c-然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是

4、该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的形式保存。二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括号处理掉。三、计算后缀表达式的值。3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：其算法思想是：从左往右按一个字节依

5、次扫描原始中缀表达式m_string，碰到连续的数字或小数点就加到string 变量str 中；如果碰到括号或操作符就将原先的str 推入队列，然后将括号或操作符赋予str，再将str 推入队列，并将str 赋予空值，依次循环进行直到扫描m_string 完成。4、转化为后缀表达式ChangeToSuffix()函数。将保存在队列中的中缀表达式转换为后缀表达式，并保存在栈中。这个函数也是整个表达式算法的关键，这里需要两个栈stack_A 和stack_B，分别在转换过程中临时存放后缀表达式的操作数与操作符。依次从中缀表达式队列que 中出列一个元素，并保存在一个string 变量str 中，然

6、后按以下几方面进行处理：如果str 是“(”，则将str 推入栈stack_B。如果str 是“)”，则要考虑stack_B 的栈顶是不是“(”，是的话就将“(”出栈stack_B；如果不是，则将stack_B 出栈一个元素（操作符），然后将其推入栈stack_A。如果str 是“+”或“-”，则要考虑有括号和优先级的情况，如果栈stack_B 为空或者栈顶为“(”，则将str 推入栈stack_B；因为操作符“+”和“-”优先级相同（谁先出现就先处理谁进栈stack_A），并且低于“*”和“/”，所以当栈stack_B 不为空并且栈顶不为“(”，则依次循环取出stack_B 的栈顶元素并依次

7、推入栈stack_A，循环结束后再将str 推入栈stack_B。如果str 是“*”或“/”，因为它们的优先级相同并且高于“+”和“-”，所以如果栈stack_B 为空或者栈顶为“+”、“-”或“(”就直接将str 推入栈stack_B；否则就将stack_B 弹出一个元素并将其推入栈stack_A 中，然后再将str 推入栈stack_B 中。除了上述情况外就只剩下操作数了，操作数就可以直接推入栈stack_A 中。注意整个过程中栈stack_B 中的元素只能是如下几种：“(”、“+”、“-”、“*”、“/”，而最终栈stack_A 保存的是后缀表达式。只有操作数和操作符，如下图所示： 注

8、意到最后返回的是stack_B 而不是stack_A，因为考虑到为了后面的计算方便，所以将其倒序保存在stack_B 中（最后一个while循环）。5、后缀表达式求值Calculate()函数。剩下的计算后缀表达式就显得非常简单了，依次将倒序的后缀表达式stack_B 弹出一个元素推入保存结果的double 类型的栈stack 中，如果遇到操作符就从栈stack 中弹出两元素进行该操作符的运算并将其结果推入到栈stack 中，依次循环进行直到栈stack_B 为空，最后栈stack 只有一个元素即为表达式的结果。八、实验报告要求实验报告应包括以下几个部分：1、设计算术表达式树的存储结构；实验中

9、采用的是二叉树的的链接存储。结点格式如下：其严格类的定义如下： template class Binarynode Please check it and try again!endl; return que; string str = ;char ch;int size = Size();bool bNumber = false;for(int i = 0; i size; i+) ch = (i); switch(ch) case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: case

10、.: bNumber = true; break; case (: case ): case +: case -: case *: case /: bNumber = false; break; default:continue; if(bNumber) str += ch; if(i=size-1) (str);else if() != 0) (str); str = ch; (str); str = ;return que;stack ExpressionType:ChangeToSuffix()叉树基本操作 2.表达式求值 0.退出程序 endl;cout endl;coutq; swi

11、tch(q) case 0: exit(0); break; case 1: 序遍历 5.叶子结点数 endl;cout 2.中序遍历 6.树的深度 endl;cout 3.后序遍历 0.退出子模块一 endl; cout 4.层序遍历 endl;cout endl; cout请分别输入二叉树的前序和中序序列:pre; cinin; while(number) cout输入功能序号:m; Binarynode* root; root=create(pre,in); switch(m) case 1: coutPreOrder:; PreOrder(root); coutendl; break;

12、 case 2: coutInOrder:; InOrder(root); coutendl; break; case 3: coutPostOrder:; PostOrder(root); coutendl; break; case 4: coutLevelOrder:; LevelOrder(root); coutendl; break; case 5: coutThe number of leaf nodes=; Leafcount(root,&c); coutcendl; break; case 6: coutThe depth of the Binary Tree=Depth(root)endl; break; case 0: goto flag; case 2: cout endl;cout 表达式求值 endl; cout 1.求值 0.退出子模块二 endl;cout endl; while(number) coutn; switch(n) case 1: coutexpression; expr=expression; coutexpression=; cout()endl; break; case 0: goto flag;