数据结构实验二叉树

实验六：二叉树及其应用

一、实验目的

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

二、问题描述

首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f

三、实验要求

如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。

四、实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境 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 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。

1 / 19

文档可能无法思考全面，请浏览后下载!

2、求值过程

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

形式保存。

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

号处理掉。

三、计算后缀表达式的值。 3、中缀表达式分解

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

2.2*(3.1+1.20)-7.5/3 队首 队尾

其算法思想是：从左往右按一个字节依次扫描原始中缀表达式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 保存的是后缀表达式。 只有操作数和操作符，如下图所示：

2 / 19

文档可能无法思考全面，请浏览后下载!

-/3栈顶-*+3.11.207.5*2.2+/2.27.531.23.1栈示意图栈底表达式二叉树

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

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

八、实验报告要求

实验报告应包括以下几个部分： 1、 设计算术表达式树的存储结构；

实验中采用的是二叉树的的链接存储。结点格式如下：

leftdataright 其严格类的定义如下：

template

class Binarynode //二叉树的结点类 { public: Binarynode():left(NULL),right(NULL){} //默认构造函数 Binarynode(const T& item,Binarynode *lptr=NULL, Binarynode *rptr=NULL):data(item),left(lptr),right(rptr){} //初始化

T data; //结点数据 Binarynode *&Left() {return left;} //取left

3 / 19

文档可能无法思考全面，请浏览后下载!

Binarynode *&Right() {return right;} //取right protected: Binarynode *left,*right; };

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

叶子结点个数算法：

template

void Leafcount(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); //右子树递归求叶子结点 } }

树的深度算法：

int Depth(Binarynode*t) //计算树的深度 {

int lh,rh; //定义左右子树的深度 if (!t) return 0; //树为空返回0 else {

lh=Depth(t->Left()); //递归调用，求左子树深度 rh=Depth(t->Right()); //递归调用，求右子树深度

if (lh>rh) //判断左右子树哪个更大，更大的深度加1返回其值 return lh+1; else

return rh+1; }

return 1;

}

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

参见九、附录，由于在报告中分析的算法，在附录源程序中省略部分注释，以免繁杂。 4、 给出程序的测试结果验证各项程序功能如下：

（1） 进入模块选择

进入模块一：

4 / 19

文档可能无法思考全面，请浏览后下载!

进入模块二：

（2） 四种遍历

以先序序列为A B D E C F ,中序序列D B E A F C为例：

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

5 / 19

文档可能无法思考全面，请浏览后下载!

（4） 求表达式的值

1、输入数据：2.2*（3.1+1.20）-7.5/3 正确结果：6.96

2、输入数据：(1+2)*3+(5+6*7); 正确输出：56

九、思考题与实验总结

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

其实利用完全二叉树的性质的存储本质上是顺序存储，但是又区别于一般的顺序存储，

6 / 19

文档可能无法思考全面，请浏览后下载!

由于树无法在顺序表直接进行存储，所以在描述二叉树的时候规定树从左到右，从上到下依次存储树结点，不存在的结点也要存储，其以0表示，对于完全二叉树来讲，只要知道结点在树中的编号，就能迅速定位该结点，但是由于要存储0来表示空结点，在结点数庞大的时候会有可能浪费空间。最后，它若要增加结点，若新增结点已超出范围，则必须要重新申请空间。

而二叉链表存储则是典型链表存储，它要利用指针来指向其左右孩子。如果要查找某一结点，必须从根出发，但是不会像利用完全二叉树的性质存储那样浪费不必要的空间。在增加结点时更容易。

综上分析，其优缺点：

完全二叉树性质存储：优点，查找结点速度快，易于理解，在结点数少的情况下，存储

方便。

缺点，存储大量结点可能会浪费大量空间，增加结点复杂。 二叉链表存储： 优点，增加结点容易，易于存储结点数比较大的树。而且指针灵

活的应用，更易与在树上进行复杂的操作。 缺点，查找结点必须从根出发，依次遍历。

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

IsWellForm()函数。判断原始中缀表达式的括号是否匹配，可以利用栈简单实现，即遇到“(”进栈，遇到“)”就从栈中弹出一个元素，直到表达式结束。如果栈为空则表示括号匹配，否则不匹配。其具体实现见附录。 下面是程序的试验：

3．实验总结

实验终于完成了，相对来说难度很大，不过由于这个是数据结构的重中之重，所以花了蛮多的心思的，树的确有很多优点，使得它如此举足轻重，它可以勾勒生活中的方方面面的关系，特别在当今社会数据关系如此复杂的情况下，它独享风光是可以理解的。不过由于它结构复杂多变，所以存储起来就颇为费劲了，这造成了我在实验中吃苦头的主要因素。实验中第一次尝试用VISIO画图表，发现它的确是个画图表的好工具。最后对于实验本身不多说了，比较满意，但是需要进一步了解树，了解编程。

十、附录

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

主程序则包含两个模块，子模块一是基于用户自己构建的二叉树的相关基本操作，包括各种遍历，求二叉树的叶子数和求树的深度。子模块二主要是表达式求值的运算，由用户输入中缀表达式，经过运算直接输出结果。下面给出以上三个文件。

1、 binarynode.h

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

#ifdef WIN32

#pragma warning(disable:4786) #endif

7 / 19

文档可能无法思考全面，请浏览后下载!

#include #include #include using namespace std; template

class Binarynode //二叉树的结点类 {

public:

Binarynode():left(NULL),right(NULL){} //默认构造函数

Binarynode(const T& item,Binarynode *lptr=NULL, Binarynode

*rptr=NULL):data(item),left(lptr),right(rptr){} //初始化二叉树

T data; //结点数据 Binarynode *&Left() {return left;} //取left Binarynode *&Right() {return right;} //取right protected:

Binarynode *left,*right; };

class ExpressionType //表达式二叉树类 {

public:

ExpressionType();

ExpressionType(string m_string);

void operator =(string m_string);//将一个字符串表达式赋予m_string double Calculate();//计算转换后的后缀表达式的值 private:

queue DivideExpressionToItem();//将原始的中缀表达式中的操作数、操作符以及括号按顺序以

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

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

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

bool IsWellForm(); //判断原始表达式中的括号是否匹配，如果匹配返回true，否则返回false。

int Size(); //返回原始表达式所包含的字节数。 private:

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

ExpressionType::ExpressionType() //构造函数 {

m_string = \"\";

8 / 19

文档可能无法思考全面，请浏览后下载!

}

ExpressionType::ExpressionType(string m_string) {

this->m_string = m_string; }

void ExpressionType::operator =(string m_string)//赋值 {

this->m_string = m_string; }

int ExpressionType::Size()//中缀表达式包含字节数 {

return m_string.size(); }

bool ExpressionType::IsWellForm()//判断表达式正确与否 {

stack 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; else

stack.pop(); break; default:break; } }

return stack.empty(); }

queue ExpressionType::DivideExpressionToItem() {

queue que;

if(!IsWellForm())// 括号是否匹配 {

cout<<\"The original expression is not well-form. Please check it and try again!\"<9 / 19

文档可能无法思考全面，请浏览后下载!

return que; }

string str = \"\"; char ch;

int size = Size(); 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 '(': 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);

10 / 19

文档可能无法思考全面，请浏览后下载!

str = ch;

que.push(str); str = \"\"; } }

return que; }

stack ExpressionType::ChangeToSuffix()//转化为后缀表达式 {

queue que; stack stack_A; stack 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 == \")\") {

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); } else {

while(!stack_B.empty() && stack_B.top() != \"(\")

11 / 19

文档可能无法思考全面，请浏览后下载!

{

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); } 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(); }

return stack_B; }

double ExpressionType::Calculate() {

stack stack_A = ChangeToSuffix();// 取得后缀表达式

12 / 19

文档可能无法思考全面，请浏览后下载!

if(stack_A.empty()) return 0;

stack 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(); 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);

13 / 19

文档可能无法思考全面，请浏览后下载!

}

break; default:

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

char* p = (char*)str.begin(); stack.push(atof(p)); break; } }

return stack.top(); }

2、 bt_algorithm.h

//该头文件主要完成二叉树的定义和基本操作 #include #include #include #include

#include \"binarynode.h\" using namespace std;

struct Element //结点类型 {

Element(){};

Element(Binarynode*t,int x,int lev):ptr(t),xOff(x),level(lev){}

Binarynode *ptr; int xOff,level; };

Binarynode*create(const string &Pres,const string& Ins) //构造函数

{

Binarynode *root; if(Pres.length()>0) {

root=new Binarynode(Pres[0]); int index=Ins.find(Pres[0]);

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

14 / 19

文档可能无法思考全面，请浏览后下载!

void PreOrder(Binarynode*t) //先序遍历 {

if (t) {

cout<data<<\" \"; PreOrder(t->Left()); PreOrder(t->Right()); } }

template

void InOrder(Binarynode*t) //{

if (t) {

InOrder(t->Left()); cout<data<<\" \"; InOrder(t->Right()); } }

template

void PostOrder(Binarynode*t) //{

if (t) {

PostOrder(t->Left()); PostOrder(t->Right()); cout<data<<\" \"; } }

template

void LevelOrder(Binarynode*t) {

queue*>Q; Binarynode *p; if (t) {

Q.push(t);

while(!Q.empty()) {

p=Q.front(); Q.pop();

cout<data<<\"\"; if(p->Left()!=NULL) Q.push(p->Left());

15 / 19

中序遍历 后序遍历 文档可能无法思考全面，请浏览后下载!

if(p->Right()!=NULL) Q.push(p->Right()); } } }

template

void Leafcount(Binarynode*t,int *c) //计算树叶子的个数 {

if (t) {

if (t->Left()==NULL&&t->Right()==NULL) {

*c=*c+1; }

Leafcount(t->Left(),c); Leafcount(t->Right(),c); } }

template

int Depth(Binarynode*t) //计算树的深度 {

int lh,rh;

if (!t) return 0; else {

lh=Depth(t->Left()); rh=Depth(t->Right()); if (lh>rh) return lh+1; else

return rh+1; }

return 1; }

3、 main

//该文件为主程序,面向用户 #include

#include \"bt_algorithm.h\" using namespace std;

Binarynode *create(const string &Pres,const string& Ins); void main() {

string pre,in;

16 / 19

文档可能无法思考全面，请浏览后下载!

int q,m,n,number,c=0; //q为模块选择;m为子模块一输入功能序号;n为子模块而输入功能序号

//number用来标记是否退出子模块;c为树叶子个数

ExpressionType expr;

string expression; //输入的中缀表达式 flag:

cout<<\" ┌────────────────────────────────┐

\"<cout<<\" │ 二叉树的操作与应用 │

\"<cout<<\" │姓名:翁恒丛 学号:6100410184 班级:计算机卓越 │

\"<cout<<\" │ │

\"<cout<<\" │1.二叉树基本操作 2.表达式求值 0.退出程序 │

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

\"<cout<<\"选择主模块:\"; cin>>q; switch(q)

{

case 0:

exit(0); break;

case 1: //模块一 {

cout<<\" ┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\"<cout<<\" ┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\"<cout<<\"请分别输入二叉树的前序和中序序列:\"<cin>>pre; cin>>in;

while(number) {

cout<<\"输入功能序号:\"<>m;

Binarynode* root;

17 / 19

文档可能无法思考全面，请浏览后下载!

root=create(pre,in); switch(m) {

case 1:

cout<<\"PreOrder:\"; PreOrder(root); cout<cout<<\"InOrder:\"; InOrder(root); cout<cout<<\"PostOrder:\"; PostOrder(root); cout<cout<<\"LevelOrder:\"; LevelOrder(root); cout<cout<<\"The number of leaf nodes=\"; Leafcount(root,&c); cout<goto flag; } } } case 2: {

cout<<\" ┏━━━━━━━━━━━━━━━━━━━━━┓\"<cout<<\" ┃ 表达式求值 ┃\"<18 / 19

文档可能无法思考全面，请浏览后下载!

{

cout<<\"输入功能序号:\"; cin>>n; switch(n) {

case 1:

cout<<\"输入表达式:\"; cin>>expression; expr=expression;

} } }

cout<cout<goto flag; } } 19 / 19