数据结构实验二叉树.docx

数据结构实验二叉树.docx

《数据结构实验二叉树.docx》由会员分享，可在线阅读，更多相关《数据结构实验二叉树.docx（29页珍藏版）》请在冰点文库上搜索。

数据结构实验二叉树

实验六：

二叉树及其应用

一、实验目的

树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。

二、问题描述

首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。

其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。

如算术表达式：

a+b*（c-d）-e/f

三、实验要求

如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。

求二叉树的深度。

十进制的四则运算的计算器可以接收用户来自键盘的输入。

由输入的表达式字符串动态生成算术表达式所对应的二叉树。

自动完成求值运算和输出结果。

四、实验环境

PC微机

DOS操作系统或Windows操作系统

TurboC程序集成环境或VisualC++程序集成环境

五、实验步骤

1、根据二叉树的各种存储结构建立二叉树；

2、设计求叶子结点个数算法和树的深度算法；

3、根据表达式建立相应的二叉树，生成表达式树的模块；

4、根据表达式树，求出表达式值，生成求值模块；

5、程序运行效果，测试数据分析算法。

六、测试数据

1、输入数据：

2.2*（3.1+1.20）-7.5/3

正确结果：

6.96

2、输入数据：

（1+2）*3+（5+6*7）;

正确输出：

56

七、表达式求值

由于表达式求值算法较为复杂，所以单独列出来加以分析：

1、主要思路：

由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。

例如有如下的中缀表达式：

a+b-c

转换成后缀表达式为：

ab+c-

然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。

如上述的后缀表达式先将a和b放入栈中，然后碰到操作符“+”，则从栈中弹出a和b进行a+b的运算，并将其结果d（假设为d）放入栈中，然后再将c放入栈中，最后是操作符“-”，所以再弹出d和c进行d-c运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。

当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。

2、求值过程

一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的形式保存。

二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括号处理掉。

三、计算后缀表达式的值。

3、中缀表达式分解

DivideExpressionToItem（）函数。

分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：

队首队尾

其算法思想是：

从左往右按一个字节依次扫描原始中缀表达式m_string，碰到连续的数字或小数点就加到string变量str中；如果碰到括号或操作符就将原先的str推入队列，然后将括号或操作符赋予str，再将str推入队列，并将str赋予空值，依次循环进行直

到扫描m_string完成。

4、转化为后缀表达式

ChangeToSuffix（）函数。

将保存在队列中的中缀表达式转换为后缀表达式，并保存在栈中。

这个函数也是整个表达式算法的关键，这里需要两个栈stack_A和stack_B，分别在转换过程中临时存放后缀表达式的操作数与操作符。

依次从中缀表达式队列que中出列一个元素，并保存在一个string变量str中，然后按以下几方面进行处理：

①如果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的栈顶元素并依次推入栈stack_A，循环结束后再将str推入栈stack_B。

④如果str是“*”或“/”，因为它们的优先级相同并且高于“+”和“-”，所以如果栈stack_B为空或者栈顶为“+”、“-”或“（”就直接将str推入栈stack_B；否则就将stack_B弹出一个元素并将其推入栈stack_A中，然后再将str推入栈stack_B中。

⑤除了上述情况外就只剩下操作数了，操作数就可以直接推入栈stack_A中。

注意整个过程中栈stack_B中的元素只能是如下几种：

“（”、“+”、“-”、“*”、“/”，而最终栈stack_A保存的是后缀表达式。

只有操作数和操作符，如下图所示：

注意到最后返回的是stack_B而不是stack_A，因为考虑到为了后面的计算方便，所以将其倒序保存在stack_B中（最后一个while循环）。

5、后缀表达式求值

Calculate（）函数。

剩下的计算后缀表达式就显得非常简单了，依次将倒序的后缀表达式stack_B弹出一个元素推入保存结果的double类型的栈stack中，如果遇到操作符就从栈stack中弹出两元素进行该操作符的运算并将其结果推入到栈stack中，依次循环进行直到栈stack_B为空，最后栈stack只有一个元素即为表达式的结果。

八、实验报告要求

实验报告应包括以下几个部分：

1、设计算术表达式树的存储结构；

实验中采用的是二叉树的的链接存储。

结点格式如下：

其严格类的定义如下：

template

classBinarynode//二叉树的结点类

{

public:

Binarynode（）:

left（NULL）,right（NULL）{}//默认构造函数

Binarynode（constT&item,Binarynode*lptr=NULL,

Binarynode*rptr=NULL）:

data（item）,left（lptr）,right（rptr）{}//初始化

Tdata;//结点数据

Binarynode*&Left（）{returnleft;}//取left

Binarynode*&Right（）{returnright;}//取right

protected:

Binarynode*left,*right;

};

2、给出二叉树中叶子结点个数算法和树的深度算法描述；

叶子结点个数算法：

template

voidLeafcount（Binarynode*t,int*c）//计算树叶子的个数

{//t为构建的树，c用来返回叶子节点个数

if（t）//树不为空

{

if（t->Left（）==NULL&&t->Right（）==NULL）//若该结点左右均为空，为叶子结点

{

*c=*c+1;

}

Leafcount（t->Left（）,c）;//左子树递归求叶子结点

Leafcount（t->Right（）,c）;//右子树递归求叶子结点

}

}

树的深度算法：

intDepth（Binarynode*t）//计算树的深度

{

intlh,rh;//定义左右子树的深度

if（!

t）return0;//树为空返回0

else

{

lh=Depth（t->Left（））;//递归调用，求左子树深度

rh=Depth（t->Right（））;//递归调用，求右子树深度

if（lh>rh）//判断左右子树哪个更大，更大的深度加1返回其值

returnlh+1;

else

returnrh+1;

}

return1;

}

3、相应的程序要给出足够的注释部分；

参见九、附录，由于在报告中分析的算法，在附录源程序中省略部分注释，以免繁杂。

4、给出程序的测试结果验证各项程序功能如下：

（1）进入模块选择

进入模块一：

进入模块二：

（2）四种遍历

以先序序列为ABDECF,中序序列DBEAFC为例：

（3）求树的叶子结点数和树的深度

（4）求表达式的值

1、输入数据：

2.2*（3.1+1.20）-7.5/3

正确结果：

6.96

2、输入数据：

（1+2）*3+（5+6*7）;

正确输出：

56

九、思考题与实验总结

1、分析利用完全二叉树的性质和二叉链表存储有什么不同？

分析其优缺点。

其实利用完全二叉树的性质的存储本质上是顺序存储，但是又区别于一般的顺序存储，由于树无法在顺序表直接进行存储，所以在描述二叉树的时候规定树从左到右，从上到下依次存储树结点，不存在的结点也要存储，其以0表示，对于完全二叉树来讲，只要知道结点在树中的编号，就能迅速定位该结点，但是由于要存储0来表示空结点，在结点数庞大的时候会有可能浪费空间。

最后，它若要增加结点，若新增结点已超出范围，则必须要重新申请空间。

而二叉链表存储则是典型链表存储，它要利用指针来指向其左右孩子。

如果要查找某一结点，必须从根出发，但是不会像利用完全二叉树的性质存储那样浪费不必要的空间。

在增加结点时更容易。

综上分析，其优缺点：

完全二叉树性质存储：

优点，查找结点速度快，易于理解，在结点数少的情况下，存储方便。

缺点，存储大量结点可能会浪费大量空间，增加结点复杂。

二叉链表存储：

优点，增加结点容易，易于存储结点数比较大的树。

而且指针灵活的应用，更易与在树上进行复杂的操作。

缺点，查找结点必须从根出发，依次遍历。

2、增加输入表达式进行语法判错的功能。

IsWellForm（）函数。

判断原始中缀表达式的括号是否匹配，可以利用栈简单实现，即遇到“（”进栈，遇到“）”就从栈中弹出一个元素，直到表达式结束。

如果栈为空则表示括号匹配，否则不匹配。

其具体实现见附录。

下面是程序的试验：

3．实验总结

实验终于完成了，相对来说难度很大，不过由于这个是数据结构的重中之重，所以花了蛮多的心思的，树的确有很多优点，使得它如此举足轻重，它可以勾勒生活中的方方面面的关系，特别在当今社会数据关系如此复杂的情况下，它独享风光是可以理解的。

不过由于它结构复杂多变，所以存储起来就颇为费劲了，这造成了我在实验中吃苦头的主要因素。

实验中第一次尝试用VISIO画图表，发现它的确是个画图表的好工具。

最后对于实验本身不多说了，比较满意，但是需要进一步了解树，了解编程。

十、附录

源程序包含三个文件，头文件binarynode.h主要给出了二叉树结点类的定义和表达式二叉树类的定义及其相关函数。

头文件bt_algorithm.h主要给出了二叉树的相关基本操作。

主程序则包含两个模块，子模块一是基于用户自己构建的二叉树的相关基本操作，包括各种遍历，求二叉树的叶子数和求树的深度。

子模块二主要是表达式求值的运算，由用户输入中缀表达式，经过运算直接输出结果。

下面给出以上三个文件。

1、binarynode.h

//该头文件主要给出二叉树结点的定义和表达式二叉树类及其相关的计算函数

#ifdefWIN32

#pragmawarning（disable:

4786）

#endif

#include

#include

#include

usingnamespacestd;

template

classBinarynode//二叉树的结点类

{

public:

Binarynode（）:

left（NULL）,right（NULL）{}//默认构造函数

Binarynode（constT&item,Binarynode*lptr=NULL,

Binarynode*rptr=NULL）:

data（item）,left（lptr）,right（rptr）{}//初始化二叉树

Tdata;//结点数据

Binarynode*&Left（）{returnleft;}//取left

Binarynode*&Right（）{returnright;}//取right

protected:

Binarynode*left,*right;

};

classExpressionType//表达式二叉树类

{

public:

ExpressionType（）;

ExpressionType（stringm_string）;

voidoperator=（stringm_string）;//将一个字符串表达式赋予m_string

doubleCalculate（）;//计算转换后的后缀表达式的值

private:

queueDivideExpressionToItem（）;//将原始的中缀表达式中的操作数、操作符以及括号按顺序以

//字符串的形式分解出来，然后保存在一个队列中

stackChangeToSuffix（）;//将队列中表示原始表达式各项的字符串调整顺序，转换成后缀表达式的

//顺序，并处理掉括号，然后保存在一个栈中

boolIsWellForm（）;//判断原始表达式中的括号是否匹配，如果匹配返回true，否则返回false。

intSize（）;//返回原始表达式所包含的字节数。

private:

stringm_string;//存储表示原始中缀表达式的字符串。

};

ExpressionType:

:

ExpressionType（）//构造函数

{

m_string="";

}

ExpressionType:

:

ExpressionType（stringm_string）

{

this->m_string=m_string;

}

voidExpressionType:

:

operator=（stringm_string）//赋值

{

this->m_string=m_string;

}

intExpressionType:

:

Size（）//中缀表达式包含字节数

{

returnm_string.size（）;

}

boolExpressionType:

:

IsWellForm（）//判断表达式正确与否

{

stackstack;

intsize=Size（）;

charch;

for（inti=0;i

{

ch=m_string.at（i）;

switch（ch）

{

case'（':

stack.push（ch）;

break;

case'）':

if（stack.empty（））

returnfalse;

else

stack.pop（）;

break;

default:

break;

}

}

returnstack.empty（）;

}

queueExpressionType:

:

DivideExpressionToItem（）

{

queueque;

if（!

IsWellForm（））//括号是否匹配

{

cout<<"Theoriginalexpressionisnotwell-form.Pleasecheckitandtryagain!

"<

returnque;

}

stringstr="";

charch;

intsize=Size（）;

boolbNumber=false;

for（inti=0;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'（':

case'）':

case'+':

case'-':

case'*':

case'/':

bNumber=false;

break;

default:

continue;

}

if（bNumber）

{

str+=ch;

if（i==size-1）

que.push（str）;

}

else

{

if（str.size（）!

=0）

que.push（str）;

str=ch;

que.push（str）;

str="";

}

}

returnque;

}

stackExpressionType:

:

ChangeToSuffix（）//转化为后缀表达式

{

queueque;

stackstack_A;

stackstack_B;

que=DivideExpressionToItem（）;//取得中缀表达式队列

if（que.empty（））

returnstack_B;

stringstr;

while（!

que.empty（））

{

str=que.front（）;

que.pop（）;

if（str=="（"）

{

stack_B.push（str）;

}

elseif（str=="）"）

{

while（!

stack_B.empty（）&&stack_B.top（）!

="（"）

{

stack_A.push（stack_B.top（））;

stack_B.pop（）;

}

if（!

stack_B.empty（））

stack_B.pop（）;

}

elseif（str=="+"||str=="-"）

{

if（stack_B.empty（）||stack_B.top（）=="（"）

{

stack_B.push（str）;

}

else

{

while（!

stack_B.empty（）&&stack_B.top（）!

="（"）

{

stack_A.push（stack_B.top（））;

stack_B.pop（）;

}

stack_B.push（str）;

}

}

elseif（str=="*"||str=="/"）

{

if（stack_B.empty（）||stack_B.top（）=="+"||stack_B.top（）=="-"||

stack_B.top（）=="（"）

{

stack_B.push（str）;

}

else

{

stack_A.push（stack_B.top（））;

stack_B.pop（）;

stack_B.push（str）;

}

}

else

stack_A.push（str）;

}

while（!

stack_B.empty（））//如果stack_B中还有操作符则将其弹出并推入stack_A

{

if（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（）;

}

returnstack_B;

}

doubleExpressionType:

:

Calculate（）

{

stackstack_A=ChangeToSuffix（）;//取得后缀表达式

if（stack_A.empty（））

return0;

stackstack;

stringstr;

charch;

doubledbl;

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（）;

stack.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=stack.top（）/dbl;

stack.pop（）;

stack.push（dbl）;

}

break;

default:

//将字符串所代表的操作数转换成双精度浮点数

//并压入栈

char*p=（char*）str.begin（）;

stack.push（atof（p））;

break;

}

}

returnstack.top（）;

}

2、bt_algorithm.h

//该头