数据结构实验二叉树

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

2、操作系统或 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、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：队首 队尾其算法思想是

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

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

7、k_B 的栈顶元素并依次推入栈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 <typename T>class Binarynode /二叉树的结点类public:Binarynode():left(NULL),right(NULL) /默认构造函数Binarynode(const T& item,Binarynode<T> *lptr=NULL,Binarynode<T> *rptr=NULL):data(item),left(lptr),right(rptr) /初始化T data; /结点数据Binarynod

10、e<T> *&Left() return left; /取leftBinarynode<T> *&Right() return right; /取rightprotected:Binarynode<T> *left,*right;2、 给出二叉树中叶子结点个数算法和树的深度算法描述；叶子结点个数算法：template<typename T>void Leafcount(Binarynode<T>*t,int *c) /计算树叶子的个数 /t为构建的树，c用来返回叶子节点个数if (t) /树不为空if (t->L

11、eft()=NULL&&t->Right()=NULL)/若该结点左右均为空，为叶子结点*c=*c+1;Leafcount(t->Left(),c); /左子树递归求叶子结点Leafcount(t->Right(),c); /右子树递归求叶子结点树的深度算法： int Depth(Binarynode<T>*t) /计算树的深度 int lh,rh; /定义左右子树的深度 if (!t) return 0; /树为空返回0 else lh=Depth(t->Left(); /递归调用，求左子树深度rh=Depth(t->Right();

12、 /递归调用，求右子树深度if (lh>rh) /判断左右子树哪个更大，更大的深度加1返回其值 return lh+1;elsereturn rh+1; return 1;3、 相应的程序要给出足够的注释部分；参见九、附录，由于在报告中分析的算法，在附录源程序中省略部分注释，以免繁杂。4、 给出程序的测试结果验证各项程序功能如下：（1） 进入模块选择进入模块一：进入模块二：（2） 四种遍历以先序序列为A B D E C F ,中序序列D B E A F C为例：（3） 求树的叶子结点数和树的深度（4） 求表达式的值1、输入数据：2.2*（3.1+1.20）-7.5/3 正确结果：6.96

13、2、输入数据：(1+2)*3+(5+6*7); 正确输出：56九、思考题与实验总结1、分析利用完全二叉树的性质和二叉链表存储有什么不同？分析其优缺点。 其实利用完全二叉树的性质的存储本质上是顺序存储，但是又区别于一般的顺序存储，由于树无法在顺序表直接进行存储，所以在描述二叉树的时候规定树从左到右，从上到下依次存储树结点，不存在的结点也要存储，其以0表示，对于完全二叉树来讲，只要知道结点在树中的编号，就能迅速定位该结点，但是由于要存储0来表示空结点，在结点数庞大的时候会有可能浪费空间。最后，它若要增加结点，若新增结点已超出范围，则必须要重新申请空间。而二叉链表存储则是典型链表存储，它要利用指针来

14、指向其左右孩子。如果要查找某一结点，必须从根出发，但是不会像利用完全二叉树的性质存储那样浪费不必要的空间。在增加结点时更容易。综上分析，其优缺点： 完全二叉树性质存储：优点，查找结点速度快，易于理解，在结点数少的情况下，存储方便。 缺点，存储大量结点可能会浪费大量空间，增加结点复杂。 二叉链表存储： 优点，增加结点容易，易于存储结点数比较大的树。而且指针灵活的应用，更易与在树上进行复杂的操作。缺点，查找结点必须从根出发，依次遍历。2、增加输入表达式进行语法判错的功能。 IsWellForm()函数。判断原始中缀表达式的括号是否匹配，可以利用栈简单实现，即遇到“(”进栈，遇到“)”就从栈中弹出一

15、个元素，直到表达式结束。如果栈为空则表示括号匹配，否则不匹配。其具体实现见附录。 下面是程序的试验：3实验总结 实验终于完成了，相对来说难度很大，不过由于这个是数据结构的重中之重，所以花了蛮多的心思的，树的确有很多优点，使得它如此举足轻重，它可以勾勒生活中的方方面面的关系，特别在当今社会数据关系如此复杂的情况下，它独享风光是可以理解的。不过由于它结构复杂多变，所以存储起来就颇为费劲了，这造成了我在实验中吃苦头的主要因素。实验中第一次尝试用VISIO画图表，发现它的确是个画图表的好工具。最后对于实验本身不多说了，比较满意，但是需要进一步了解树，了解编程。十、附录源程序包含三个文件，头文件bina

16、rynode.h主要给出了二叉树结点类的定义和表达式二叉树类的定义及其相关函数。头文件bt_algorithm.h主要给出了二叉树的相关基本操作。主程序则包含两个模块，子模块一是基于用户自己构建的二叉树的相关基本操作，包括各种遍历，求二叉树的叶子数和求树的深度。子模块二主要是表达式求值的运算，由用户输入中缀表达式，经过运算直接输出结果。下面给出以上三个文件。1、 binarynode.h/该头文件主要给出二叉树结点的定义和表达式二叉树类及其相关的计算函数#ifdef WIN32#pragma warning(disable:4786)#endif#include <string>#

17、include <stack>#include <queue>using namespace std;template <typename T>class Binarynode /二叉树的结点类public:Binarynode():left(NULL),right(NULL) /默认构造函数Binarynode(const T& item,Binarynode<T> *lptr=NULL,Binarynode<T> *rptr=NULL):data(item),left(lptr),right(rptr) /初始化二叉树T

18、data; /结点数据Binarynode<T> *&Left() return left; /取leftBinarynode<T> *&Right() return right; /取rightprotected:Binarynode<T> *left,*right;class ExpressionType /表达式二叉树类public:ExpressionType();ExpressionType(string m_string);void operator =(string m_string);/将一个字符串表达式赋予m_stringd

19、ouble Calculate();/计算转换后的后缀表达式的值private:queue<string> DivideExpressionToItem();/将原始的中缀表达式中的操作数、操作符以及括号按顺序以 / 字符串的形式分解出来，然后保存在一个队列中stack<string> ChangeToSuffix(); /将队列中表示原始表达式各项的字符串调整顺序，转换成后缀表达式的 /顺序，并处理掉括号，然后保存在一个栈中bool IsWellForm(); /判断原始表达式中的括号是否匹配，如果匹配返回true，否则返回false。int Size(); /返回原

20、始表达式所包含的字节数。private:string m_string; /存储表示原始中缀表达式的字符串。;ExpressionType:ExpressionType() /构造函数m_string = ""ExpressionType:ExpressionType(string m_string)this->m_string = m_string;void ExpressionType:operator =(string m_string)/赋值this->m_string = m_string;int ExpressionType:Size()/中缀表达式

21、包含字节数return m_string.size();bool ExpressionType:IsWellForm()/判断表达式正确与否stack<char> stack;int size = Size();char ch;for(int i = 0; i < size; i+)ch = m_string.at(i);switch(ch)case '(':stack.push(ch);break;case ')':if(stack.empty()return false;elsestack.pop();break;default:break

22、;return stack.empty();queue<string> ExpressionType:DivideExpressionToItem()queue<string> que;if(!IsWellForm()/ 括号是否匹配cout<<"The original expression is not well-form. Please check it and try again!"<<endl;return que;string str = ""char ch;int size = Size();

23、bool bNumber = false;for(int i = 0; i < size; i+)ch = m_string.at(i);switch(ch)case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':case '.':bNumber = true;break;case '

24、(':case ')':case '+':case '-':case '*':case '/':bNumber = false;break;default:continue;if(bNumber)str += ch;if(i=size-1)que.push(str);elseif(str.size() != 0)que.push(str);str = ch;que.push(str);str = ""return que;stack<string> ExpressionTyp

25、e:ChangeToSuffix()/转化为后缀表达式queue<string> que;stack<string> stack_A;stack<string> stack_B;que = DivideExpressionToItem(); / 取得中缀表达式队列if(que.empty()return stack_B;string str;while(!que.empty()str = que.front();que.pop();if(str = "(")stack_B.push(str);else if(str = ")&q

26、uot;)while(!stack_B.empty() && stack_B.top()!= "(")stack_A.push(stack_B.top();stack_B.pop();if(!stack_B.empty()stack_B.pop();else if(str = "+" | str = "-")if(stack_B.empty() | stack_B.top() = "(")stack_B.push(str);elsewhile(!stack_B.empty() &&

27、stack_B.top() != "(")stack_A.push(stack_B.top();stack_B.pop();stack_B.push(str);else if(str = "*" | str = "/")if(stack_B.empty() | stack_B.top() = "+" | stack_B.top() = "-" |stack_B.top() = "(")stack_B.push(str);elsestack_A.push(stack_B.top

28、();stack_B.pop();stack_B.push(str);elsestack_A.push(str);while(!stack_B.empty() / 如果stack_B中还有操作符则将其弹出并推入stack_Aif(stack_B.top() != "(")stack_A.push(stack_B.top();stack_B.pop();while(!stack_A.empty()stack_B.push(stack_A.top();stack_A.pop();return stack_B;double ExpressionType:Calculate()st

29、ack<string> stack_A = ChangeToSuffix();/ 取得后缀表达式if(stack_A.empty()return 0;stack<double> stack;string str;char ch;double dbl;while(!stack_A.empty()str = stack_A.top();stack_A.pop();ch = str.at(0);switch(ch)case '+':dbl = stack.top();stack.pop();dbl += stack.top();stack.pop();stac

30、k.push(dbl);break;case '-':dbl = stack.top();stack.pop();dbl = stack.top() - dbl;stack.pop();stack.push(dbl);break;case '*':dbl = stack.top();stack.pop();dbl *= stack.top();stack.pop();stack.push(dbl);break;case '/':dbl = stack.top();stack.pop();if(dbl != 0.000) / 除数不为0！dbl =

31、 stack.top() / dbl;stack.pop();stack.push(dbl);break;default:/ 将字符串所代表的操作数转换成双精度浮点数/ 并压入栈char* p = (char*)str.begin();stack.push(atof(p);break;return stack.top();2、 bt_algorithm.h/该头文件主要完成二叉树的定义和基本操作#include <iostream>#include <stack>#include <queue>#include <iomanip>#include

32、 "binarynode.h"using namespace std;struct Element /结点类型Element();Element(Binarynode<char>*t,int x,int lev):ptr(t),xOff(x),level(lev)Binarynode <char> *ptr;int xOff,level;Binarynode<char>*create(const string &Pres,const string& Ins) /构造函数Binarynode<char> *roo

33、t;if(Pres.length()>0)root=new Binarynode<char>(Pres0);int index=Ins.find(Pres0);root->Left()=create(Pres.substr(1,index),Ins.substr(0,index);root->Right()=create(Pres.substr(index+1),Ins.substr(index+1);else root=NULL;return root;template<typename T>void PreOrder(Binarynode<T

34、>*t) /先序遍历if (t)cout<<t->data<<" "PreOrder(t->Left();PreOrder(t->Right(); template<typename T>void InOrder(Binarynode<T>*t) /中序遍历if (t)InOrder(t->Left();cout<<t->data<<" "InOrder(t->Right();template<typename T>void Po

35、stOrder(Binarynode<T>*t) /后序遍历if (t)PostOrder(t->Left();PostOrder(t->Right();cout<<t->data<<" "template<typename T>void LevelOrder(Binarynode<T>*t)queue<Binarynode<T>*>Q;Binarynode<T> *p;if (t)Q.push(t);while(!Q.empty()p=Q.front();Q.

36、pop();cout<<p->data<<""if(p->Left()!=NULL)Q.push(p->Left();if(p->Right()!=NULL)Q.push(p->Right();template<typename T>void Leafcount(Binarynode<T>*t,int *c) /计算树叶子的个数if (t)if (t->Left()=NULL&&t->Right()=NULL)*c=*c+1;Leafcount(t->Left()

37、,c);Leafcount(t->Right(),c);template<typename T>int Depth(Binarynode<T>*t) /计算树的深度int lh,rh;if (!t) return 0;elselh=Depth(t->Left();rh=Depth(t->Right();if (lh>rh) return lh+1;elsereturn rh+1;return 1;3、 main/该文件为主程序,面向用户#include <string>#include "bt_algorithm.h&quo

38、t;using namespace std;Binarynode<char> *create(const string &Pres,const string& Ins);void main()string pre,in;int q,m,n,number,c=0; /q为模块选择;m为子模块一输入功能序号;n为子模块而输入功能序号 /number用来标记是否退出子模块;c为树叶子个数 ExpressionType expr; string expression; /输入的中缀表达式flag:cout<<" "<<endl;c

39、out<<" 二叉树的操作与应用 "<<endl;cout<<" 姓名:翁恒丛 学号:6100410184 班级:计算机卓越 "<<endl;cout<<" "<<endl;cout<<" 1.二叉树基本操作 2.表达式求值 0.退出程序 "<<endl;cout<<" "<<endl;cout<<"选择主模块:"cin>>q; switch(q)case 0:exit(0);break; case 1: /模块一 cout<<" "<<endl;cout<<" 二叉树基本操作 "<<endl;cout<<" 1.先序遍历 5.叶子结点数 "<<endl;cout<<" 2.中序遍历 6.树的深度 "<<endl;cout<<" 3.后序遍历