数据结构实验二叉树.docx

数据结构实验二叉树.docx

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

数据结构实验二叉树

实验六：

二叉树及其应用

一、实验目的

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

二、问题描述

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

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

如算术表达式：

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

三、实验要求

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

求二叉树的深度。

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

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

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

四、实验环境

PC微机

DOS操作系统或Windows操作系统

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

五、实验步骤

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

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

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

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

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

六、测试数据

1、输入数据：

*（+）3

正确结果：

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

Pleasecheckitandtryagain!

"<

returnque;

}

stringstr="";

charch;

intsize=Size（）;

boolbNumber=false;

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

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="";

}

}

returnque;

}

stackExpressionType:

:

ChangeToSuffix（）叉树基本操作2.表达式求值0.退出程序│"<

cout<<"└────────────────────────────────┘"<

cout<<"选择主模块:

";

cin>>q;

switch（q）

{

case0:

exit（0）;

break;

case1:

序遍历5.叶子结点数┃"<

cout<<"┃2.中序遍历6.树的深度┃"<

cout<<"┃3.后序遍历0.退出子模块一┃"<

cout<<"┃4.层序遍历┃"<

cout<<"┗━━━━━━━━━━━━━━━━━━━━━━━━━┛"<

cout<<"请分别输入二叉树的前序和中序序列:

"<

cin>>pre;

cin>>in;

while（number）

{

cout<<"输入功能序号:

"<

cin>>m;

Binarynode*root;

root=create（pre,in）;

switch（m）

{

case1:

cout<<"PreOrder:

";

PreOrder（root）;

cout<

break;

case2:

cout<<"InOrder:

";

InOrder（root）;

cout<

break;

case3:

cout<<"PostOrder:

";

PostOrder（root）;

cout<

break;

case4:

cout<<"LevelOrder:

";

LevelOrder（root）;

cout<

break;

case5:

cout<<"Thenumberofleafnodes=";

Leafcount（root,&c）;

cout<

break;

case6:

cout<<"ThedepthoftheBinaryTree="<

break;

case0:

gotoflag;

}

}

}

case2:

{

cout<<"┏━━━━━━━━━━━━━━━━━━━━━┓"<

cout<<"┃表达式求值┃"<

cout<<"┃1.求值0.退出子模块二┃"<

cout<<"┗━━━━━━━━━━━━━━━━━━━━━┛"<

while（number）

{

cout<<"输入功能序号:

";

cin>>n;

switch（n）

{

case1:

cout<<"输入表达式:

";

cin>>expression;

expr=expression;

cout<

cout<<（）<

break;

case0:

gotoflag;

}

}

}

}

}