《数据结构实验二叉树》由会员分享，可在线阅读，更多相关《数据结构实验二叉树（18页珍藏版）》请在金锄头文库上搜索。
1、实验六：二叉树及其应用一、实验目的树是数据结构中应用极为广泛的非线性结构， 本单元的实验达到熟悉二叉树的存储结构 的特性，以及如何应用树结构解决具体问题。二、问题描述首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。 其次， 以二叉树表示算 术表达式的基础上，设计一个十进制的四则运算的计算器。如算术表达式： a+b*(c-d)-e/f三、实验要求如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。 求二叉树的深度。 十进制的四则运算的计算器可以接收用户来自键盘的输入。 由输入 的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实
2、验环境PC微机DOS操作系统或 Windows操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境五、实验步骤1、根据二叉树的各种存储结构建立二叉树；2、设计求叶子结点个数算法和树的深度算法；3、根据表达式建立相应的二叉树，生成表达式树的模块；4、根据表达式树，求出表达式值，生成求值模块；5、程序运行效果，测试数据分析算法。六、测试数据1、输入数据： 2.2* ( 3.1+1.20 ) -7.5/3正确结果： 6.962、输入数据： (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、中缀表达式分解DivideExpressionToltem() 函数。分解出原始中缀表达式中的操作数、操作符以及括号,保存在队列中，以本实验中的数据为例，
5、分解完成后队列中的保存顺序如下图所示：2.2*(3.1+1.20)-7.5/3队首队尾其算法思想是：从左往右按一个字节依次扫描原始中缀表达式m_string，碰到连续的数字或小数点就加到string 变量str中；如果碰到括号或操作符就将原先的str推入队列，然后将括号或操作符赋予str，再将str推入队列，并将str赋予空值，依次循环进行直到扫描m_string 完成。4、转化为后缀表达式ChangeToSufix()函数。将保存在队列中的中缀表达式转换为后缀表达式，并保存在栈中。这个函数也是整个表达式算法的关键，这里需要两个栈stack_A和stack_B，分别在转换过程中临时存放后缀表达
6、式的操作数与操作符。依次从中缀表达式队列que中出列一个元素，并保存在一个 string 变量str中，然后按以下几方面进行处理： 如果str是(”，则将str推入栈stack_B。 如果str是“)”，则要考虑stack_B的栈顶是不是“(”，是的话就将“(”出栈stack_B ；如果不是，则将stack_B出栈一个元素(操作符)，然后将其推入栈stack_A。 如果str是“+”或“-”，则要考虑有括号和优先级的情况，如果栈stack_B为空或者栈顶为“(”，则将str推入栈stack_B ;因为操作符“ +”和“-”优先级相同(谁先出现 就先处理谁进栈stack_A )，并且低于“ *
7、”和“ / ”，所以当栈stack_B不为空并且栈顶不 为“(”，则依次循环取出stack_B的栈顶元素并依次推入栈stack_A，循环结束后再将str推入栈stack_B。 如果str是“ * ”或“/”，因为它们的优先级相同并且高于“+”和“-”，所以如果栈stack_B为空或者栈顶为“ +”、“-”或(就直接将str推入栈stack_B ;否则就将stack_B 弹出一个元素并将其推入栈 stack_A中，然后再将str推入栈stack_B中。 除了上述情况外就只剩下操作数了，操作数就可以直接推入栈stack_A中。注意整个过程中栈stack_B中的元素只能是如下几种：“ (”、“ +”
8、、“ - ”、“ * ”、“ /”，而最终 栈stack_A保存的是后缀表达式。只有操作数和操作符，如下图所示：栈顶栈底表达式二叉树注意到最后返回的是 stack_B而不是stack_A ,因为考虑到为了后面的计算方便，所以将其倒序保存在stack_B中（最后一个while循环）。5、后缀表达式求值Calculate。 函数。剩下的计算后缀表达式就显得非常简单了，依次将倒序的后缀表达式stack_B弹出一个元素推入保存结果的 double类型的栈stack中，如果遇到操作符就 从栈stack中弹出两元素进行该操作符的运算并将其结果推入到栈 stack中，依次循环进 行直到栈stack_B为空，
9、最后栈stack只有一个元素即为表达式的结果。八、实验报告要求实验报告应包括以下几个部分：1、设计算术表达式树的存储结构；实验中采用的是二叉树的的链接存储。结点格式如下：leftdataright其严格类的定义如下：template class Binarynode/二叉树的结点类public:Binaryno de():left(NULL),right(NULL)/ 默认构造函数Binaryno de(c onst T& item,B inaryno de *lptr=NULL,Bin ary no de *rptr=NULL):data(item),left(lptr),right (rp
10、tr)/ 初始化T data;II结点数据Bin ary node *&Left() return left; II 取 leftBinarynode *&Right() return right; II 取 rightprotected:Binarynode *left,*right;2、给出二叉树中叶子结点个数算法和树的深度算法描述； 叶子结点个数算法：templatevoid Leafcount(Binarynode*t,int *c)/ 计算树叶子的个数 /t 为构建的树， c 用来返回叶子节点个数if (t) / 树不为空if (t-Left()=NULL&t-Right()=NUL
11、L)/ 若该结点左右均为空， 为叶子结点 *c=*c+1;Leafcount(t-Left(),c); / 左子树递归求叶子结点 Leafcount(t-Right(),c); / 右子树递归求叶子结点 树的深度算法：int Depth(Binarynode*t)/ 计算树的深度int lh,rh;/ 定义左右子树的深度if (!t) return 0;/ 树为空返回 0else lh=Depth(t-Left(); / 递归调用，求左子树深度 rh=Depth(t-Right(); / 递归调用，求右子树深度 if (lhrh) /判断左右子树哪个更大，更大的深度加1 返回其值return
12、lh+1;elsereturn rh+1;return 1;3、相应的程序要给出足够的注释部分； 参见九、附录，由于在报告中分析的算法，在附录源程序中省略部分注释，以免繁杂。4、给出程序的测试结果验证各项程序功能如下： ( 1 ) 进入模块选择进入模块一：姓名嗡恒丛曇暮更誥缶活曙班级:计算机卓趣二叉树基本操作2.表达式求值缜退岀程序选择王模块汽先中后层 12 3 4数块占屠结探子子的出叶舉 二叉树基本操作560青分别输入二災树的前序和中序序列:进入模块二:姓名;翁恒丛二叔树的操作与应用学号：6100410184班级二计算机卓越i.-X树基本操作表达式求值0.退出程序先择主豎I .求值表达式賢缰
13、岀子模块二 會入功能序号；1 1(2) 四种遍历以先序序列为AB D ECF中序序列DB EAF C为例:历历历历 先中后层 12 3 4请分别输入二叉树的前序和中序序列=ABDEGFDBEAFG输入功頁游号：1PFeOi*dei*：fi B D E C F输入功自綁号：InOrde p： D B E A F C 输入功能序号3PostOrder：D E B F C A 输入昉能浄号：4Leue lOidjei： ABCDEF 输入功青卽F号：(3) 求树的叶子结点数和树的深度PostOrder：D E B F C A 输入动能浄号：4LeueLOrder：ABCDEFJ he niimbeF
14、 of leaf ndes=3 輸入功頁第号；The depth of the Binary Ti*ee=3端入功盲翁号=历历历历 H 先中后层 ! 12 3 4二叉树基本操作吕.S.0.氐结虜数 勰輙一请分别输入二叉树的前序和中序序列匕ABDECFDBEAFC输入功頁孙号；1PreOrder：A B D E C F输入功胃济号，2lnOrcle ip ：D B E A P C输入功能序号：(4) 求表达式的值1、输入数据：2.2*( 3.1 + 1.20) -7.5/3正确结果：6.962、输入数据：(1+2)*3+(5+6*7);正确输出：56班级匕计算机卓越乩退岀程序姓名:翁恒丛1. 二叉树基本操作二昱树的操作与应用61004101842-表达式求值选择王模块認输入表 K：*3+*3+5+6*7)=56Lk&1球值 L少可罷出子模块二:号:1 ?2_2*-7.5/32.2*-7.5/3=6_96输入动能序号:九、思考题与实验总结1、分析利用完全二叉树的
