数据结构课程设计说明书树应用树和二叉树转换.docx

数据结构课程设计说明书树应用树和二叉树转换.docx

《数据结构课程设计说明书树应用树和二叉树转换.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计说明书树应用树和二叉树转换.docx（33页珍藏版）》请在冰点文库上搜索。

数据结构课程设计说明书树应用树和二叉树转换

中北大学

数据结构与算法课程设计

说明书

学院、系：

软件学院

专业：

软件工程

班级：

1314010xxx

学生姓名：

学号：

1314010xxx

设计题目：

树的应用

起迄日期:

2015年1月12日-2015年1月29日

指导教师:

尹四清

 2015年1月29日

一、需求分析

1.设计内容及设计要求

A.设计内容：

（1）建立一棵树；

（2）将树转换成二叉树；

（3）实现二叉树的前序、中序、后序的递归和非递归遍历算法。

B.设计要求：

（1）符合课题要求，实现相应功能；

（2）要求界面友好美观，操作方便易行；

（3）注意程序的实用性、安全性；

2.本演示程序中，元素为单个字符，以空格表示空树（即结点为空），以回车符作为输入结束标志，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。

在真实的运行过程中，由用户手动输入待创建树的含有空格的先根次序序列，并按回车结束，程序会将其转化为其对应的二叉树，然后对二叉树进行先序、中序、后序的递归及非递归遍历以及层序遍历，然后显示转化后二叉树的高度和总结点数，以验证所创建的二叉树是否正确，最后，销毁创建的树和二叉树，程序结束。

3.演示程序以用户和计算机对话方式执行，即在计算机终端（屏幕）上显示“提示信息”之后，由用户在键盘上输入演示程序规定的运算命令，相应的输入数据和运算结果显示在其后。

4.为了美观，程序的输出结果采用了分块显示的模式，由虚线及标题隔开，便于用户检查和验证。

5.测试数据

如图，给出一棵树，若屏幕上显示如下信息：

->请按树的先根次序输入序列，如有空子树，用空格填充，完成后输入回车确认

此时，你应当输入：

（↙表示回车确认）

ABEFCDGHIJK↙

提示：

为方便确认输入了几个空格，用星号’*’表示输入序列中的空格，则序列如下

ABE*F**C*DGHI*J*K******↙（不是真实的输入序列，供计算需输入空格个数时用）

这时，建好的树的先根和后根次序序列如下：

树的先根序列ABEFCDGHIJK

树的后根序列EFBCIJKHGDA

由树和二叉树的转换关系知，二叉树的先序和中序遍历所得序列分别与树的先根和后根遍历所得序列相同，据此验证转化是否正确。

二叉树的先序和中序遍历序列如下：

二叉树先序序列ABEFCDGHIJK

二叉树中序序列EFBCIJKHGDA

2、概要设计

为了实现上述程序功能，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。

为此，需要两个抽象数据类型，树和二叉树的抽象数据类型。

1.树的抽象数据类型定义

ADTTree{ 

 数据对象D：

D是具有相同特性的数据元素的集合。

数据关系R：

若D为空集，则称为空树； 

       若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系：

（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；  

（2）若D-{root}≠Φ，则存在D-{root}的一个划分D1,D2,D3, „,Dm（m>0），

对于任意j≠k（1≤j,k≤m）有Dj∩Dk=Φ,且对任意的i（1≤i≤m），

唯一存在数据元素xi∈Di有∈H;

（3）对应于D-{root}的划分，H-{,„,}有唯一的一个划分

H1，H2,„,Hm（m>0），对任意j≠k（1≤j,k≤m）有Hj∩Hk=Φ，且对任意i

（1≤i≤m）,Hi是Di上的二元关系，（Di,{Hi}）是一棵符合本定义的树，

称为根root的子树。

 基本操作P：

InitTree（&T）; 

操作结果：

构造空树T。

DestroyTree（&T）; 

初始条件：

树T存在。

操作结果：

销毁树T。

CreateTree（&T,definition）; 

初始条件：

definition给出树T的定义。

操作结果：

按definition构造树T。

ClearTree（&T）; 

初始条件：

树T存在。

操作结果：

将树T清为空树。

TreeEmpty（T）; 

初始条件：

树T存在。

操作结果：

若T为空树，则返回TRUE，否则返回FALSE。

TreeDepth（T）; 

初始条件：

树T存在。

操作结果：

返回Ｔ的深度。

Root（T）; 

初始条件：

树T存在。

操作结果：

返回T的根。

Value（T,cur_e）; 

初始条件：

树T存在，cur_e是T中某个结点。

操作结果：

返回cur_e的值。

Assign（T,cur_e,value）; 

初始条件：

树T存在，cur_e是T中某个结点。

操作结果：

结点cur_e赋值为value。

Parent（T,cur_e）; 

初始条件：

树T存在，cur_e是T中某个结点。

操作结果：

若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。

LeftChild（T,cur_e）; 

初始条件：

树T存在，cur_e是T中某个结点。

操作结果：

若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。

RightSibling（T,cur_e）; 

初始条件：

树T存在，cur_e是T中某个结点。

操作结果：

若cur_e有右兄弟，则返回它的右兄弟，否则返回“空”。

InsertChild（&T,&p,I,c）; 

初始条件：

树Ｔ存在，ｐ指向Ｔ中某个结点，1≤i≤p指结点的度＋１，非空树ｃ与Ｔ不相交。

操作结果：

插入c为Ｔ中ｐ指结点的第ｉ棵子树。

DeleteChild（&T,&p,i）; 

初始条件：

树T存在，p指向T中某个结点，1≤i≤p指结点的度。

操作结果：

删除Ｔ中ｐ所指结点的第ｉ棵子树。

TraverseTree（T,visit（））; 

初始条件：

树T存在，visit是对结点操作的应用函数。

操作结果：

按某种次序对T的每个结点调用函数visit（）一次且至多一次。

一旦visit（）失败，则操作失败。

}ADT Tree

2.二叉树的抽象数据类型定义

ADTBinaryTree{

数据对象D：

D是具有相同特性的数据元素的集合。

数据关系R：

若D=Φ，则R=Φ，称BinaryTree为空二叉树；

若D≠Φ，则R={H}，H是如下二元关系；

（1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；

（2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr=Φ；

（3）若D1≠Φ，则D1中存在惟一的元素x1，∈H，且存在D1上的关系H1⊆H；若Dr≠Φ，则Dr中存在惟一的元素xr，∈H，且存在上的关系Hr⊆H；H={,,H1,Hr}；

（4）（D1,{H1}）是一棵符合本定义的二叉树，称为根的左子树；（Dr,{Hr}）是一棵符合本定义的二叉树，称为根的右子树。

基本操作：

InitBiTree（&T）

操作结果：

构造空二叉树T。

DestroyBiTree（&T）

初始条件：

二叉树T已存在。

操作结果：

销毁二叉树T。

CreateBiTree（&T,definition）

初始条件：

definition给出二叉树T的定义。

操作结果：

按definiton构造二叉树T。

ClearBiTree（&T）

初始条件：

二叉树T存在。

操作结果：

将二叉树T清为空树。

BiTreeEmpty（T）

初始条件：

二叉树T存在。

操作结果：

若T为空二叉树，则返回TRUE，否则返回FALSE。

BiTreeDepth（T）

初始条件：

二叉树T存在。

操作结果：

返回T的深度。

Root（T）

初始条件：

二叉树T存在。

操作结果：

返回T的根。

Value（T,e）

初始条件：

二叉树T存在，e是T中某个结点。

操作结果：

返回e的值。

Assign（T,&e,value）

初始条件：

二叉树T存在，e是T中某个结点。

操作结果：

结点e赋值为value。

Parent（T,e）

初始条件：

二叉树T存在，e是T中某个结点。

操作结果：

若e是T的非根结点，则返回它的双亲，否则返回“空”。

LeftChild（T,e）

初始条件：

二叉树T存在，e是T中某个结点。

操作结果：

返回e的左孩子。

若e无左孩子，则返回“空”。

RightChild（T,e）

初始条件：

二叉树T存在，e是T中某个结点。

操作结果：

返回e的右孩子。

若e无右孩子，则返回“空”。

LeftSibling（T,e）

初始条件：

二叉树T存在，e是T中某个结点。

操作结果：

返回e的左兄弟。

若e是T的左孩子或无左兄弟，则返回“空”。

RightSibling（T,e）

初始条件：

二叉树T存在，e是T中某个结点。

操作结果：

返回e的右兄弟。

若e是T的右孩子或无右兄弟，则返回“空”。

InsertChild（T,p,LR,c）

初始条件：

二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。

操作结果：

根据LR为0或1，插入c为T中p所指结点的左或右子树。

p所指结点的原有左或右子树则成为c的右子树。

DeleteChild（T,p,LR）

初始条件：

二叉树T存在，p指向T中某个结点，LR为0或1。

操作结果：

根据LR为0或1，删除T中p所指结点的左或右子树。

PreOrderTraverse（T,visit（））

初始条件：

二叉树T存在，Visit是对结点操作的应用函数。

操作结果：

先序遍历T，对每个结点调用函数Visit一次且仅一次。

一旦visit（）失败，则操作失败。

InOrderTraverse（T,visit（））

初始条件：

二叉树T存在，Visit是对结点操作的应用函数。

操作结果：

中序遍历T，对每个结点调用函数Visit一次且仅一次。

一旦visit（）失败，则操作失败。

PostOrderTraverse（T,visit（））

初始条件：

二叉树T存在，Visit是对结点操作的应用函数。

操作结果：

后序遍历T，对每个结点调用函数Visit一次且仅一次。

一旦visit（）失败，则操作失败。

LevelOrderTraverse（T,visit（））

初始条件：

二叉树T存在，Visit是对结点操作的应用函数。

操作结果：

层次遍历T，对每个结点调用函数Visit一次且仅一次。

一旦visit（）失败，则操作失败。

}ADTBinaryTree

3.本程序包括个模块

【1】主程序模块

先声明一棵树和一棵二叉树，然后输入树的含空格先根次序序列，构建一棵树，然后将其转化为二叉树，并对二叉树进行先序、中序、后序的递归和非递归遍历以及层序遍历，然后输出二叉树的高度和总结点数，最后销毁这两棵树。

【2】建立树模块——按照树的先根序列创建树。

【3】树转化二叉树模块——将树转化为二叉树。

【4】二叉树的遍历——二叉树的先序、中序、后序的递归和非递归遍历以及层序遍历。

【5】二叉树的相关信息——二叉树的高度和总结点数。

【6】销毁树和二叉树模块——销毁创建的树和转换出的二叉树。

【7】栈和队列的模块——供二叉树先序、中序、后序的非递归算法调用

各模块之间关系：

3、详细设计

1.元素类型、结点类型和指针类型

树的结点元素类型设置为字符型，这样既可以接收字符也可以接受数字。

typedefcharTElemType;//树中结点元素类型

//----------------二叉树的二叉链表存储表示--------------------

typedefstructBiNode{

TElemTypedata;//数据域,存储结点名称

structBiNode*lchild,*rchild;//孩子结点指针

}BiNode,*BiTree;

二叉树的二叉链表表示法示意图：

//-------------------树的孩子兄弟表示法-----------------------

typedefstructCSNode{

TElemTypedata;//数据域,存储结点名称

structCSNode*firstchild,*nextsibling;//孩子指针域和兄弟指针域

}CSNode,*CSTree;

树的孩子兄弟表示法示意图：

2.构造一般树算法：

按照树的先根次序序列构建一棵树：

对于这棵树，按照需求分析第1页的测试数据，用户应当输入（↙表示回车确认）

ABEFCDGHIJK↙

正确输入所需序列后，树的建立完成。

StatusCreateCSTree（CSTree&CT）{//按先根序列构造树

//按先根次序输入树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示树T

charch;

ch=getchar（）;

if（ch==''）

CT=NULL;

else{

if（!

（CT=（CSNode*）malloc（sizeof（CSNode））））{

printf（"内存分配失败！

\n"）;

exit（OVERFLOW）;

}//if

CT->data=ch;//生成根结点

CreateCSTree（CT->firstchild）;//构建左子树

CreateCSTree（CT->nextsibling）;//构建右子树

}//else

returnOK;

}//CreateCSTree

3.转换为二叉树

树和二叉树的转换关键在于树的二叉链表与其对应的二叉树的二叉链表是相同的，只是对同一个二叉链表的解释不同，二叉树的数据域存放结点名称，左指针域指向左孩子，右指针域指向右孩子；树的数据域存放结点名称，左指针域指向孩子结点，右指针域指向与该结点相邻的一个兄弟结点。

当两者具有相同的存储结构时，便可以完成转换，转换过程的实质是按照二叉树的定义将二叉链表解释为二叉树的过程。

StatusExchangeToBiTree（CSTree&CT,BiTree&T）{

//将一棵用二叉链表表示的树递归地转换为二叉树

if（!

CT）//树CT为空时，二叉树T为空

T=NULL;

else{

//若树的对应结点不空，申请内存空间

if（!

（T=（BiNode*）malloc（sizeof（BiNode））））{

printf（"内存分配失败！

\n"）;

exit（OVERFLOW）;

}//if

//将树的数据域复制到二叉树对应的数据域

T->data=CT->data;

//若树的孩子域不为空，则用树的孩子域创建二叉树的左子树

ExchangeToBiTree（CT->firstchild,T->lchild）;

//若树的兄弟域不为空，则用树的兄弟域创建二叉树的右子树

ExchangeToBiTree（CT->nextsibling,T->rchild）;

}//else

}//ExchangeToBiTree

4.二叉树的遍历

二叉树有先序、中序、后序、层序四种遍历方式，而先序、中序、后序遍历又有递归和非递归两种算法，总共有7个遍历算法。

其中，先序、中序、后序非递归遍历算法需要用到栈，层序遍历需要使用队列，队列和栈的相关定义和算法请参考详细设计P21。

二叉树先序、中序、后序遍历的区别仅在于访问根结点的时机不同，而层序遍历则是逐层从左到右访问每一个结点。

先序遍历二叉树算法的框架是：

若二叉树为空，则空操作；

否则访问根结点（D）；先序遍历左子树（L）；先序遍历右子树（R）。

中序遍历二叉树算法的框架是：

若二叉树为空，则空操作；

否则中序遍历左子树（L）；访问根结点（D）；中序遍历右子树（R）。

后序遍历二叉树算法的框架是：

若二叉树为空，则空操作；

否则后序遍历左子树（L）；后序遍历右子树（R）；访问根结点（D）。

虽然访问根结点的时机不同，但是先左后右的规则并没有改变。

所有的遍历函数都调用元素访问函数Visit，他们的参数列表中均含有一个函数指针变量Status（*Visit）（TElemType），通过主函数向他们传递元素访问函数Visit的函数名，就可以实现按元素访问函数Visit设定格式输出的目的。

这样的好处在于当输出格式改变时，只需修改元素访问函数Visit的输出格式而无需更改7个遍历函数，做到一改全改。

以下是所有遍历算法的实现以及元素访问函数Visit：

//-----------------------元素访问函数Visit-------------------------

StatusPrintElement（TElemTypee）{//输出元素e的值

printf（"%c",e）;//元素类型设定为字符型

returnOK;

}//PrintElement

//--------------------------递归算法--------------------------------

StatusPreOrderTraverse（BiTreeT,Status（*Visit）（TElemType））{//先序遍历递归算法

//采用二叉链表存储结构，Visit是对数据元素操作的应用函数

//先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit

if（T）{

if（Visit（T->data））//访问根结点

if（PreOrderTraverse（T->lchild,Visit））//访问左子树

if（PreOrderTraverse（T->rchild,Visit））//访问右子树

returnOK;

returnERROR;

}//if

elsereturnOK;

}//PreOrderTraverse

StatusInOrderTraverse（BiTreeT,Status（*Visit）（TElemType））{//中序遍历递归算法

//采用二叉链表存储结构，Visit是对数据元素操作的应用函数

//中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit

if（T）{

if（InOrderTraverse（T->lchild,Visit））//访问左子树

if（Visit（T->data））//访问根结点

if（InOrderTraverse（T->rchild,Visit））//访问右子树

returnOK;

returnERROR;

}//if

elsereturnOK;

}//InOrderTraverse

StatusPostOrderTraverse（BiTreeT,Status（*Visit）（TElemType））{//后序遍历递归算法

//采用二叉链表存储结构，Visit是对数据元素操作的应用函数

//后序遍历二叉树T的递归算法，对每个数据元素调用函数Visit

if（T）{

if（PostOrderTraverse（T->lchild,Visit））//访问左子树

if（PostOrderTraverse（T->rchild,Visit））//访问右子树

if（Visit（T->data））//访问根结点

returnOK;

returnERROR;

}//if

elsereturnOK;

}//PostOrderTraverse

//-----------------------非递归遍历算法---------------------------

StatusPreOrderTraverse1（BiTreeT,Status（*Visit）（TElemType））{//先序遍历非递归算法

//采用二叉链表存储结构，Visit是对数据元素操作的应用函数

//先序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit

StackS;

InitStack（S）;//初始化栈

BiTreep=T;//设置工作指针p并对其赋初值

while（p||!

（StackEmpty（S）））{

if（p）{

if（!

Visit（p->data））//访问根结点

returnERROR;

Push（S,p）;//根指针进栈

p=p->lchild;//遍历左子树

}//if

else{

Pop（S,p）;//根指针退栈

p=p->rchild;//遍历右子树

}//else

}//while

returnOK;

}//PreOrderTraverse1

StatusInOrderTraverse1（BiTreeT,Status（*Visit）（TElemType））{//中序遍历非递归算法

//采用二叉链表存储结构，Visit是对数据元素操作的应用函数

//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit

StackS;

InitStack（S）;

BiTreep=T;

while（p||!

（StackEmpty（S）））{

if（p）{

Push（S,p）;//根指针进栈

p=p->lchild;//遍历左子树

}//if

else{

Pop（S,p）;//根指针退栈

if（!

Visit（p->data））//访问根结点

returnERROR;

p=p->rchild;//遍历右子树

}//else

}//while

returnOK;

}//InOrderTraverse1

StatusPostOrderTraverse1（BiTreeT,Status（*Visit）（TElemType））{//后序遍历非递归算法

//采用二叉链表存储结构，Visit是对数据元素操作的应用函数

//后序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit