- -中北大学数据构造与算法课程设计说 明 书学 院、系：软件学院专 业：软件工程班 级：1314010xxx学 生 姓 名：学 号：1314010xxx设 计 题 目：树的应用起 迄 日 期:2015年1月12日- 2015年1月29日指 导 教 师:四清2015 年1月 29 日一、需求分析1.设计容及设计要求 A.设计容： 1建立一棵树； 2将树转换成二叉树； 3实现二叉树的前序、中序、后序的递归和非递归遍历算法。 B.设计要求： (1) 符合课题要求，实现相应功能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、平安性；2.本演示程序中，元素为单个字符，以空格表示空树(即结点为空)，以回车符作为输入完毕标志，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。在真实的运行过程中，由用户手动输入待创立树的含有空格的先根次序序列，并按回车完毕，程序会将其转化为其对应的二叉树，然后对二叉树进展先序、中序、后序的递归及非递归遍历以及层序遍历，然后显示转化后二叉树的高度和总结点数，以验证所创立的二叉树是否正确，最后，销毁创立的树和二叉树，程序完毕。3.演示程序以用户和计算机对话方式执行，即在计算机终端屏幕上显示“提示信息之后，由用户在键盘上输入演示程序规定的运算命令，相应的输入数据和运算结果显示在其后。4.为了美观，程序的输出结果采用了分块显示的模式，由虚线及标题隔开，便于用户检查和验证。5.测试数据 如图，给出一棵树，假设屏幕上显示如下信息： -请按树的先根次序输入序列，如有空子树，用空格填充，完成后输入回车确认 此时，你应当输入：表示回车确认 ABE F C DGHI J K 提示：为方便确认输入了几个空格，用星号*表示输入序列中的空格，那么序列如下 ABE*F*C*DGHI*J*K*不是真实的输入序列，供计算需输入空格个数时用 这时，建好的树的先根和后根次序序列如下：树的先根序列 A B E F C D G H I J K树的后根序列 E F B C I J K H G D A 由树和二叉树的转换关系知，二叉树的先序和中序遍历所得序列分别与树的先根和后根遍历所得序列一样，据此验证转化是否正确。二叉树的先序和中序遍历序列如下：二叉树先序序列 A B E F C D G H I J K二叉树中序序列 E F B C I J K H G D A2、 概要设计为了实现上述程序功能，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。为此，需要两个抽象数据类型，树和二叉树的抽象数据类型。1.树的抽象数据类型定义ADT Tree数据对象D：D是具有一样特性的数据元素的集合。 数据关系R：假设D为空集，那么称为空树；假设D仅含有一个数据元素，那么R为空集，否那么R=H，H是如下二元关系： (1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2)假设D-root，那么存在D-root的一个划分D1,D2,D3,Dm(m0)， 对于任意jk(1j,km)有DjDk=,且对任意的i(1im)， 唯一存在数据元素xiDi有H; (3)对应于D-root的划分，H-,有唯一的一个划分 H1，H2,Hm(m0)，对任意jk(1j,km)有HjHk=，且对任意i (1im),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); 初始条件：树存在，指向中某个结点，1ip指结点的度，非空树与不相交。 操作结果：插入c为中指结点的第棵子树。 DeleteChild(&T,&p,i); 初始条件：树T存在，p指向T中某个结点，1ip指结点的度。 操作结果：删除中所指结点的第棵子树。 TraverseTree(T,visit(); 初始条件：树T存在，visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数visit( )一次且至多一次。一旦visit( )失败，那么操作失败。ADTTree2.二叉树的抽象数据类型定义ADT BinaryTree 数据对象D：D是具有一样特性的数据元素的集合。 数据关系R： 假设D=，那么R=，称BinaryTree为空二叉树； 假设D，那么R=H，H是如下二元关系； 1在D中存在惟一的称为根的数据元素root，它在关系H下无前驱； 2假设D-root，那么存在D-root=D1,Dr，且D1Dr =； 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中某个结