《数据结构课程设计报告说明书树的应用树和二叉树的转换》由会员分享，可在线阅读，更多相关《数据结构课程设计报告说明书树的应用树和二叉树的转换（29页珍藏版）》请在金锄头文库上搜索。
1、- -中北大学数据构造与算法课程设计说 明 书学 院、系：软件学院专 业：软件工程班 级：1314010xxx学 生 姓 名：学 号：1314010xxx设 计 题 目：树的应用起 迄 日 期:2015年1月12日- 2015年1月29日指 导 教 师:四清2015 年1月 29 日一、需求分析1.设计容及设计要求 A.设计容： 1建立一棵树； 2将树转换成二叉树； 3实现二叉树的前序、中序、后序的递归和非递归遍历算法。 B.设计要求： (1) 符合课题要求，实现相应功能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、平安性；2.本演示程序中，元素为单个字符，以空格表示
2、空树(即结点为空)，以回车符作为输入完毕标志，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。在真实的运行过程中，由用户手动输入待创立树的含有空格的先根次序序列，并按回车完毕，程序会将其转化为其对应的二叉树，然后对二叉树进展先序、中序、后序的递归及非递归遍历以及层序遍历，然后显示转化后二叉树的高度和总结点数，以验证所创立的二叉树是否正确，最后，销毁创立的树和二叉树，程序完毕。3.演示程序以用户和计算机对话方式执行，即在计算机终端屏幕上显示“提示信息之后，由用户在键盘上输入演示程序规定的运算命令，相应的输入数据和运算结果显示在其后。4.为了美观，程序的输出结果采用了分块显示的模式，由虚线及标题隔
3、开，便于用户检查和验证。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 由树和二叉树的转换关系知，二叉树的先序和中序遍历所得序列分别与树的先根
4、和后根遍历所得序列一样，据此验证转化是否正确。二叉树的先序和中序遍历序列如下：二叉树先序序列 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下无前驱
5、； (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,defin
6、ition); 初始条件：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);
7、初始条件：树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有右兄弟，那么返回它的右兄弟，否那么返回“空。 Inser
8、tChild(&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是具有
9、一样特性的数据元素的集合。 数据关系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 )
10、操作结果：构造空二叉树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
11、( 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中某个结
