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

中北大学数据结构与算法课程设计说明书学院、系：软件学院专业：软件工程班级：1314010xxx学生姓名：学号：1314010xxx设计题目：树的应用起迄日期:2015年1月12日-2015年1月29日指导教师:尹四清2015年1月29日1一、需求分析1.设计内容及设计要求A.设计内容：（1）建立一棵树；（2）将树转换成二叉树；（3）实现二叉树的前序、中序、后序的递归和非递归遍历算法。B.设计要求：(1)符合课题要求，实现相应功能；(2)要求界面友好美观，操作方便易行；(3)注意程序的实用性、安全性；2.本演示程序中，元素为单个字符，以空格表示空树(即结点为空)，以回车符作为输入结束标志，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。在真实的运行过程中，由用户手动输入待创建树的含有空格的先根次序序列，并按回车结束，程序会将其转化为其对应的二叉树，然后对二叉树进行先序、中序、后序的递归及非递归遍历以及层序遍历，然后显示转化后二叉树的高度和总结点数，以验证所创建的二叉树是否正确，最后，销毁创建的树和二叉树，程序结束。3.演示程序以用户和计算机对话方式执行，即在计算机终端（屏幕）上显示“提示信息”之后，由用户在键盘上输入演示程序规定的运算命令，相应的输入数据和运算结果显示在其后。4.为了美观，程序的输出结果采用了分块显示的模式，由虚线及标题隔开，便于用户检查和验证。5.测试数据如图，给出一棵树，若屏幕上显示如下信息：-请按树的先根次序输入序列，如有空子树，用空格填充，完成后输入回车确认此时，你应当输入：（↙表示回车确认）ABEFCDGHIJK↙提示：为方便确认输入了几个空格，用星号’*’表示输入序列中的空格，则序列如下ABE*F**C*DGHI*J*K******↙（不是真实的输入序列，供计算需输入空格个数时用）这时，建好的树的先根和后根次序序列如下：树的先根序列ABEFCDGHIJK树的后根序列EFBCIJKHGDA2由树和二叉树的转换关系知，二叉树的先序和中序遍历所得序列分别与树的先根和后根遍历所得序列相同，据此验证转化是否正确。二叉树的先序和中序遍历序列如下：二叉树先序序列ABEFCDGHIJK二叉树中序序列EFBCIJKHGDA二、概要设计为了实现上述程序功能，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。为此，需要两个抽象数据类型，树和二叉树的抽象数据类型。1.树的抽象数据类型定义ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠Φ，则存在D-{root}的一个划分D1,D2,D3,„,Dm(m0)，对于任意j≠k(1≤j,k≤m)有Dj∩Dk=Φ,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有root,xi∈H;(3)对应于D-{root}的划分，H-{root,xi,„,root,xm}有唯一的一个划分H1，H2,„,Hm(m0)，对任意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);3初始条件：树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为Ｔ中ｐ指结点的第ｉ棵子树。4DeleteChild(&T,&p,i);初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。操作结果：删除Ｔ中ｐ所指结点的第ｉ棵子树。TraverseTree(T,visit());初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。}ADTTree2.二叉树的抽象数据类型定义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，root,x1∈H，且存在D1上的关系H1⊆H；若Dr≠Φ，则Dr中存在惟一的元素xr，root,xr∈H，且存在上的关系Hr⊆H；H={root,x1,root,xr,H1,Hr}；（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。基本操作：InitBiTree(&T)操作结果：构造空二叉树T。DestroyBiTree(&T)初始条件：二叉树T已存在。操作结果：销毁二叉树T。CreateBiTree(&T,definition)初始条件：definition给出二叉树T的定义。操作结果：按definiton构造二叉树T。5ClearBiTree(&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的左孩子或无左兄弟，则返回“空”。6RightSibling(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()失败，则操作失败。}ADTBinaryTree73.本程序包括个模块【1】主程序模块先声明一棵树和一棵二叉树，然后输入树的含空格先根次序序列，构建一棵树，然后将其转化为二叉树，并对二叉树进行先序、中序、后序的递归和非递归遍历以及层序遍历，然后输出二叉树的高度和总结点数，最后销毁这两棵树。【2】建立树模块——按照树的先根序列创建树。【3】树转化二叉树模块——将树转化为二叉树。【4】二叉树的遍历——二叉树的先序、中序、后序的递归和非递归遍历以及层序遍历。【5】二叉树的相关信息——二叉树的高度和总结点数。【6】销毁树和二叉树模块——销毁创建的树和转换出的二叉树。【7】栈和队列的模块——供二叉树先序、中序、后序的非递归算法调用各模块之间关系：三、详细设计1.元素类型、结点类型和指针类型树的结点元素类型设置为字符型，这样既可以接收字符也可以接受数字。typedefcharTElemType;//树中结点元素类型8//----------------二叉树的二叉链表存储表示--------------------typedefstructBiNode{TElemTypedata;//数据域,存储结点名称structBiNode*lchild,*rchild;//孩子结点指针}BiNode,*BiTree;二叉树的二叉链表表示法示意图：//-------------------树的孩子兄弟表示法-----------------------typedefstructCSNode{TElemTypedata;//数据域,存储结点名称structCSNode*firstchild,*nextsibling;//孩子指针域和兄弟指针域}CSNode,*CSTree;树的孩子兄弟表示法示意图：92.构造一般树算法：按照树的先根次序序列构建一棵树：对于这棵树，按照需求分析第1页的测试数据，用户应当输入（↙表示回车确认）ABEFCDGHIJK↙正确输入所需序列后，树的建立完成。StatusCreateCSTree(CSTree&CT){//按先根序列构造树//按先根次序输入树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示树Tcharch;ch=getchar();if(ch=='')CT=NULL