毕业设计-数据结构树的应用-树和二叉树的转换.doc

《毕业设计-数据结构树的应用-树和二叉树的转换.doc》由会员分享，可在线阅读，更多相关《毕业设计-数据结构树的应用-树和二叉树的转换.doc（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构与算法课程设计说 明 书学 院、系：软件学院专 业：软件工程班 级： 学 生 姓 名：学 号： 设 计 题 目：树的应用 起 迄 日 期:2015年1月12日- 2015年1月29日指 导 教 师: 2015 年1月 29 日一、需求分析1.设计内容及设计要求 A.设计内容： （1）建立一棵树； （2）将树转换成二叉树； （3）实现二叉树的前序、中序、后序的递归和非递归遍历算法。 B.设计要求： (1) 符合课题要求，实现相应功能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、安全性；2.本演示程序中，元素为单个字符，以空格表示空树(即结点为空)，以回车符作为

2、输入结束标志，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。在真实的运行过程中，由用户手动输入待创建树的含有空格的先根次序序列，并按回车结束，程序会将其转化为其对应的二叉树，然后对二叉树进行先序、中序、后序的递归及非递归遍历以及层序遍历，然后显示转化后二叉树的高度和总结点数，以验证所创建的二叉树是否正确，最后，销毁创建的树和二叉树，程序结束。3.演示程序以用户和计算机对话方式执行，即在计算机终端（屏幕）上显示“提示信息”之后，由用户在键盘上输入演示程序规定的运算命令，相应的输入数据和运算结果显示在其后。4.为了美观，程序的输出结果采用了分块显示的模式，由虚线及标题隔开，便于用户检查和验证。5

3、.测试数据 如图，给出一棵树，若屏幕上显示如下信息： -请按树的先根次序输入序列，如有空子树，用空格填充，完成后输入回车确认 此时，你应当输入：（表示回车确认） 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 A二、 概要设计为了实现上述程序功能，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。为此，需要两个抽象数据类型，树和二叉树的抽象数据类型。1.树的抽象数据类型定义ADT Tree数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R=H，H是如下二元关系： (1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2)若D-root

5、，则存在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); 初始条件：d

6、efinition给出树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

7、中某个结点。 操作结果：结点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); 初始条件

8、：树存在，指向中某个结点，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=

9、，则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。 DestroyBiTre

10、e( &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的根

11、。 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的

12、右孩子。若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的右

13、子树。 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

14、()失败，则操作失败。 PostOrderTraverse( T, visit() ) 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。 LevelOrderTraverse( T, visit() ) 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 操作结果：层次遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。 ADT BinaryTree 3. 本程序包括个模块【1】主程序模块 先声明一棵树和一棵二叉树，然后输入树的含空格先根次序

15、序列，构建一棵树，然后将其转化为二叉树，并对二叉树进行先序、中序、后序的递归和非递归遍历以及层序遍历，然后输出二叉树的高度和总结点数，最后销毁这两棵树。【2】建立树模块按照树的先根序列创建树。【3】树转化二叉树模块将树转化为二叉树。【4】二叉树的遍历二叉树的先序、中序、后序的递归和非递归遍历以及层序遍历。【5】二叉树的相关信息二叉树的高度和总结点数。【6】销毁树和二叉树模块销毁创建的树和转换出的二叉树。【7】栈和队列的模块供二叉树先序、中序、后序的非递归算法调用各模块之间关系：三、 详细设计1. 元素类型、结点类型和指针类型 树的结点元素类型设置为字符型，这样既可以接收字符也可以接受数字。 t

16、ypedef char TElemType; /树中结点元素类型/-二叉树的二叉链表存储表示- typedef struct BiNodeTElemType data; /数据域,存储结点名称struct BiNode *lchild,*rchild; /孩子结点指针 BiNode,*BiTree;二叉树的二叉链表表示法示意图：/-树的孩子兄弟表示法- typedef struct CSNode TElemType data; /数据域,存储结点名称 struct CSNode *firstchild, *nextsibling; /孩子指针域和兄弟指针域 CSNode, *CSTree;树的

17、孩子兄弟表示法示意图：2. 构造一般树算法：按照树的先根次序序列构建一棵树：对于这棵树，按照需求分析第1页的测试数据，用户应当输入（表示回车确认） ABE F C DGHI J K 正确输入所需序列后，树的建立完成。Status CreateCSTree(CSTree &CT) /按先根序列构造树 /按先根次序输入树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示树Tchar ch;ch=getchar();if(ch= ) CT=NULL;elseif(!(CT=(CSNode *)malloc(sizeof(CSNode)printf(内存分配失败！n);exit(OVERFLO

18、W); /ifCT-data=ch; /生成根结点 CreateCSTree(CT-firstchild); /构建左子树 CreateCSTree(CT-nextsibling); /构建右子树 /else return OK; /CreateCSTree3. 转换为二叉树 树和二叉树的转换关键在于树的二叉链表与其对应的二叉树的二叉链表是相同的，只是对同一个二叉链表的解释不同，二叉树的数据域存放结点名称，左指针域指向左孩子，右指针域指向右孩子；树的数据域存放结点名称，左指针域指向孩子结点，右指针域指向与该结点相邻的一个兄弟结点。当两者具有相同的存储结构时，便可以完成转换，转换过程的实质是按照

19、二叉树的定义将二叉链表解释为二叉树的过程。Status ExchangeToBiTree(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-

20、firstchild,T-lchild); /若树的兄弟域不为空，则用树的兄弟域创建二叉树的右子树 ExchangeToBiTree(CT-nextsibling,T-rchild); /else /ExchangeToBiTree4. 二叉树的遍历二叉树有先序、中序、后序、层序四种遍历方式，而先序、中序、后序遍历又有递归和非递归两种算法，总共有7个遍历算法。其中，先序、中序、后序非递归遍历算法需要用到栈，层序遍历需要使用队列，队列和栈的相关定义和算法请参考详细设计P21。二叉树先序、中序、后序遍历的区别仅在于访问根结点的时机不同，而层序遍历则是逐层从左到右访问每一个结点。先序遍历二叉树算法的

21、框架是： 若二叉树为空，则空操作； 否则 访问根结点 (D)； 先序遍历左子树 (L)； 先序遍历右子树 (R)。中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (D)； 中序遍历右子树 (R)。后序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (D)。虽然访问根结点的时机不同，但是先左后右的规则并没有改变。所有的遍历函数都调用元素访问函数Visit，他们的参数列表中均含有一个函数指针变量Status(* Visit)(TElemType)，通过主函数向他们传递元素访

22、问函数Visit的函数名，就可以实现按元素访问函数Visit设定格式输出的目的。这样的好处在于当输出格式改变时，只需修改元素访问函数Visit的输出格式而无需更改7个遍历函数，做到一改全改。以下是所有遍历算法的实现以及元素访问函数Visit：/-元素访问函数Visit- Status PrintElement(TElemType e) /输出元素e的值 printf( %c ,e); /元素类型设定为字符型return OK;/PrintElement/-递归算法- Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType) /先序遍

23、历递归算法 /采用二叉链表存储结构，Visit是对数据元素操作的应用函数/先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit if(T)if(Visit(T-data) /访问根结点 if(PreOrderTraverse(T-lchild,Visit) /访问左子树 if(PreOrderTraverse(T-rchild,Visit) /访问右子树 return OK; return ERROR; /ifelse return OK;/PreOrderTraverseStatus InOrderTraverse(BiTree T,Status(* Visit)(TElemType

24、) /中序遍历递归算法 /采用二叉链表存储结构，Visit是对数据元素操作的应用函数/中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit if(T)if(InOrderTraverse(T-lchild,Visit) /访问左子树 if(Visit(T-data) /访问根结点 if(InOrderTraverse(T-rchild,Visit) /访问右子树 return OK; return ERROR; /ifelse return OK;/InOrderTraverse Status PostOrderTraverse(BiTree T,Status(* Visit)(TEl

25、emType) /后序遍历递归算法 /采用二叉链表存储结构，Visit是对数据元素操作的应用函数/后序遍历二叉树T的递归算法，对每个数据元素调用函数Visit if(T)if(PostOrderTraverse(T-lchild,Visit) /访问左子树 if(PostOrderTraverse(T-rchild,Visit) /访问右子树 if(Visit(T-data) /访问根结点 return OK; return ERROR;/ifelse return OK;/PostOrderTraverse/-非递归遍历算法-Status PreOrderTraverse1(BiTree T

26、,Status(* Visit)(TElemType) /先序遍历非递归算法 /采用二叉链表存储结构，Visit是对数据元素操作的应用函数/先序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit Stack S;InitStack(S); /初始化栈BiTree p=T; /设置工作指针p并对其赋初值while(p|!(StackEmpty(S)if(p)if(!Visit(p-data) /访问根结点 return ERROR;Push(S,p); /根指针进栈 p=p-lchild; /遍历左子树/ifelsePop(S,p); /根指针退栈 p=p-rchild; /遍历右子树

27、/else/whilereturn OK; /PreOrderTraverse1Status InOrderTraverse1(BiTree T,Status(* Visit)(TElemType) /中序遍历非递归算法 /采用二叉链表存储结构，Visit是对数据元素操作的应用函数/中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit Stack S;InitStack(S);BiTree p=T;while(p|!(StackEmpty(S)if(p)Push(S,p); /根指针进栈 p=p-lchild; /遍历左子树/ifelsePop(S,p); /根指针退栈 if(!Vi

28、sit(p-data) /访问根结点 return ERROR;p=p-rchild; /遍历右子树 /else/whilereturn OK; /InOrderTraverse1Status PostOrderTraverse1(BiTree T,Status(* Visit)(TElemType) /后序遍历非递归算法 /采用二叉链表存储结构，Visit是对数据元素操作的应用函数/后序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit BiTree p=T, q=NULL; / int n=0; Stack s; InitStack(s); while(p)|(!StackEmpt

29、y(s) while(p) Push(s,p); p=p-lchild; /while q=NULL;while(!StackEmpty(s)GetTop(s, p);if(p-rchild=NULL)|(p-rchild=q) if(!Visit(p-data) /访问根结点 return ERROR; if(p=T) return ERROR;q=p; Pop(s,p);/ifelse p=p-rchild;break;/else/while /whilereturn OK; /PostOrderTraverse1Status LevelOrderTraverse1(BiTree T,St

30、atus(* Visit)(TElemType) /层序遍历非递归算法 /采用二叉链表存储结构，Visit是对数据元素操作的应用函数/层序遍历二叉树T的算法，对每个数据元素调用函数Visit Queue Q;BiTree p=T;if(T) /根结点入队列 InitQueue(Q); /初始化队列 EnQueue(Q,T); while(!QueueEmpty(Q) /队列不空 DeQueue(Q,p); if(!Visit(p-data) /访问根结点 return ERROR; if(p-lchild) EnQueue(Q,p-lchild); /左孩子入队列 if(p-rchild) E

31、nQueue(Q,p-rchild); /右孩子入队列 /while printf(n); /ifreturn OK; /LevelOrderTraverse15.二叉树的信息int BiTreeDepth(BiTree T) /递归求二叉树高度 /若二叉树T存在，返回T的深度（高度），否则返回0int Thigh,leftThigh,rightThigh; /分别表示二叉树高度，左子树高度，右子树高度if(!T) return 0; /树高为0elseleftThigh=BiTreeDepth(T-lchild); /求左子树高度 rightThigh=BiTreeDepth(T-rchil

32、d); /求右子树高度 if(leftThigh=rightThigh) /求二叉树高度 Thigh=leftThigh+1;else Thigh=rightThigh+1; /elsereturn Thigh;/BiTreeDepthint NodeSubNum(BiTree T) /统计二叉树的结点个数 if(!T) return 0; /二叉树为空树，没有结点 else return(NodeSubNum(T-lchild)+NodeSubNum(T-rchild)+1); /NodeSubNum6.销毁树 void DestoryCSTree(CSTree &CT)/按照树的定义递归地

33、销毁树if(CT) /非空树 if(CT-firstchild) /孩子子树非空 DestoryCSTree(CT-firstchild);if(CT-nextsibling) /兄弟子树非空 DestoryCSTree(CT-nextsibling); free(CT); /释放根结点CT=NULL; /空指针赋0 /if /DestoryTreevoid DestoryBiTree(BiTree &T)/按照二叉树定义递归地销毁二叉树if(T) /非空树 if(T-lchild) /左子树非空,销毁左子树 DestoryBiTree(T-lchild);if(T-rchild) /右子树非

34、空,销毁右子树 DestoryBiTree(T-rchild); free(T); /释放根结点T=NULL; /空指针赋0 /if /DestoryTreevoid DestoryTree(CSTree &CT,BiTree &T)/销毁树和二叉树DestoryCSTree(CT);DestoryBiTree(T);printf(-生成的树和二叉树已被销毁！); /DestoryTree7. 栈和队列的定义及算法/-栈的顺序存储表示- typedef BiTree SElemType; /栈的元素为二叉树指针类型 typedef struct /栈的顺序存储表示 SElemType *bas

35、e; /栈底指针，在栈构造之前和销毁之后，base的值为NULL SElemType *top; /栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位 Stack; /-队列的链式存储表示- typedef BiTree QElemType; /队列元素为二叉树指针类型typedef struct QNode /链队列的C语言表示 QElemType data; /数据域 struct QNode * next; /指针域 QNode,* QueuePtr;typedef structQueuePtr front; /队头指针 QueuePtr rear; /队尾指针

36、Queue; /-栈的相关函数(供非递归后序遍历使用)-Status InitStack(Stack &S)/构造一个空的顺序栈 if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)printf(内存分配失败！n);exit(OVERFLOW); S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; /InitStackStatus DestoryStack(Stack &S)/释放顺序栈S所占内存空间 free(S.base);S.base=NULL;S.top=NULL; return OK; /DestoryStackStatus StackEmpty(Stack S)/判断顺序栈S是否为空栈,是返回1，否返回0 return S.top=S.base; /StackIsEmptyStatus Push(Stack &S,SElemType e) /入栈 if(S.top-S.base = S.stacksize)if(!(S.base=(SElemType *)realloc