树与二叉树转换的实现3.docx

《树与二叉树转换的实现3.docx》由会员分享，可在线阅读，更多相关《树与二叉树转换的实现3.docx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河南工程学院数据结构与算法课程设计成果报告树与二叉树转换的实现子树，从根开始一直向右，遇到的右子树均依次作为树的子树(二叉树中结点的 右子树中变为该结点右侧的兄弟)，将树转化成二叉树。void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)树转化为二叉树 ctroot指向树的根结点，btroot,指向二叉树的根(QueueCTree *VisitedCTreeNodes;QueueBTree *VisitedBTreeNodes;辅助队歹UinitQueueCTree(VisitedCTreeNodes);initQueueBTree(Vis

2、itedBTreeNodes);/初始化队歹 UCTreeNode *ctnode;BTreeNode *btnode,*p,*LastSibling;int i;btroot=(BTreeNode *)malloc(sizeof(BTreeNode);/添力口开辟内存空 间语句btroot-data=ctroot-data; 树的根结点作为二叉树的根结点 btroot-lchild=btroot-rchild=NULL;addQueueCTree(VisitedCTreeNodesctroot);/树 的根结 点入队 addQueueBTree(VisitedBTreeNodes,btroo

3、t);/二叉树的根结点入队 while(!QueueCTreeEmpty(VisitedCTreeNodes)(ctnode = delQueueCTree(VisitedCTreeNodes);/树结,点出队btnode = delQueueBTree(VisitedBTreeNodes);/二叉树结,点出队 for(i=0;ichildreni=NULL) 孩子结点访问完毕break;p=(BTreeNode *)malloc(sizeof(BTreeNode);/分配二叉树结点 p-data=ctnode-childreni-data;p-lchild=p-rchild=NULL;if(

4、i=0)btnode-lchild=p;长子，作为父结点的做孩子elseLastSibling-rchild=p; 作为上一个兄弟结点的右孩子LastSibling=p;addQueueCTree(VisitedCTreeNodes,ctnode-children1);/树结点进队列addQueueBTree(VisitedBTreeNodes,p);/二又树结点进门队歹 U)void Preorder(BTreeNode *T)(if(T)(coutT-dataPreorder(T-lchild);Preorder(T-rchild);)3程序清单初始化树(双亲表示法) void init_

5、ptree(PTree *tree) ( -tree-count=-l;)初始化树结点(孩子兄弟表示法)BTNode GetTreeNode(int x)(BTNode t;t.data=x;t.firstchild=t.rightsib=NULL; return t;树的前序遍历(递归)void preorder(BTNode *T)(if(T!=NULL)(printf(%d ,T-data);preorder(T-firstchild);preorder(T-rightsib);)树的前序遍历(非递归)void preorder2(PTree T) (int i,j=0;BTNode p

6、MAX_TREE_SIZE;BTNode *ip,*is,*ir,*Tree;ip=(BTNode *)malloc(sizeof(BTNode);is=(BTNode *)malloc(sizeof(BTNode);ir=(BTNode *)malloc(sizeof(BTNode);Tree=(BTNode *)malloc(sizeof(BTNode);for(i=0;iT.count;i+)(pi=GetTreeNode(T.nodei.data);)for(i=l;idata) (9j+;is=&pj;)if(!(is-firstchild)(is-firstchild=ip; ir

7、=ip；)elseir-rightsib=ip; ir=ip;)Tree=&p0;return Tree;)/*主菜单*/void Menu()printf(= printf。* 输入 1 printf。*输入 2- printf(”*输入 3printf(= printf。* 输入 1 printf。*输入 2- printf(”*输入 3printf( printf( printf( printf(“* * *ii * * *输入4-输入5-输入6:输入0二主菜单=n“）；- 以双亲法创立一棵一般树*n“）； 树的前序遍历（递归）*n）;- 树的后序遍历（递归）*n“）； 树的前序遍历（非

8、递归）*n“）; 树的后序遍历（非递归）*n”）;- 层次序的非递归遍历*n“）；退出程序* *printf(= printf(”请输入执行的指令/*副菜单*/void Menu2()nH);-=nH);printf( 5I， n II ).printf( 5I， n II ).printf(printf(“* * *“* * *返回主菜单继续操作*n）;退出程序*n”）/*主函数*/ void main() int i=0,cl,c2;PTree T;BTNode *Tree; init_ptree(&T);loop: Menu();scanfCd&cl);switch(cl)iocase

9、1:printf(建立一般树/衣次输入各个结点情况:n)；printf(“输入结点方式:双亲数据，整型数据(第一个结点双亲数据为为最后以-1,-1 结束)n 例子:-LI l,3nM)；T=CreatTree(T);Tree=change(T);print一般树转换成二叉树后的情况:n“)；PrintBTree(TreeJ); getchar();break;case 2:printf(“树的前序遍历(递归):n);preorder(Tree);printf(n);break;case 3:printf(树的后序遍历(递归):n);inoeder(Tree);printfCXn);break;

10、case 4:printf(树的前序遍历俳递归):n“);preorder2(T);printf(n);break;case 5:printf(树的后序遍历俳递归):n);inoeder2(T);printf(n);break;case 6:printf(树的层次遍历:rT);level(T);printf(n);break;case 0:exit ；break;)Menu2();scanf(%d，&c2);if(c2=9)goto loop;else if(c2=0)exit(l);114测试输入执行的命令之后得到树的层次遍历。如图4.1-问x|u: D:CYuYanbinwwtemp.ex

11、e*二 * 二 * 二 树一一 般i一3二 二 二 二 二二 二 二 二 二*_二 二 二 二 二 二 二二 二 二 二 二 二 二历. 12 3 4k*9返 回 主菜单继续操作*退 出 fe.,序*xy *x*x图4. 1树的层次遍历输入执行的命令之后得到树的前序遍历。如图4.2行的指令：2 遍历递归:行的指令：2 遍历递归:raiD:CYuYanbin.wwtemp .exe,般树转换成二叉树后的情况: 1w w wQ二4副是单 xxxxxxxxxxxxxxxxxxx 返回王茎单继续操作* 退出程序 XXXXXXXXXXXXXXXXX输分 输入 WA 必 朝八主菜单=-阪粉坪藤/一至祠E树

12、的前序遍历（递归* 的序遍历序遍历（遍历递递 可一二，* * 333昌 11 菜单 X X WX M X XX X X X X M X XX X返回至菜单继续操作*图4. 2树的前序遍历12输入执行的命令之后得到树的后序遍历。如图4.3I P：cI P：c. In x1艮由程芹XAkMWXAX请施入执行的指令：2 树的前序遍历递归:返向全卷单继续操作*15.出程 序 *WM4T嗡入1输入2备入3瑜入4u = nn = n主菜单nu=nu=以双养法创立一棵一般梃 a的前序遍历，遢归 * 的后皮遍历璇启） 的前在调厉琲递归* 的唐存通原牛逸归）* 次序的罪递归遍历*迟出售序清前入执行的指令门 树的

13、后序遍历递归:4 2 3 1mmx9WMM0讴而圭关单继续操作图4. 3树的后序遍历135总结通过本次课程设计，我明白了有关一个课题的所有知识不仅是在课本上，而 且还要多查阅一些资料才能够更好的完成课题，这就需要一种能力，即自学能力。 本次课程设计还让我认识到自己的缺点。我选的是设计树与二叉树转换的相关函 数库，刚开始认为会很简单，但到后来就出现一些难以解决的问题，就向同学请 教，并查阅相关资料。经过慢慢的调试，最终测试成功。这次课程设计让我所学 到的数据结构知识发挥的淋漓尽致，而且还拓展了我的知识面，使我更加熟练的 掌握各种方法。总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对

14、数据 结构更加了解。14参考文献.数据结构（C语言版）严蔚敏清华大学出版社20021 .数据结构 语言描述王路群中国水利水电出版社2007.数据结构实验教程（C语言版）王国钧清华大学出版社20092 .数据结构题集严蔚敏，吴伟民编 清华大学出版社200215题目树与二叉树转换的实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代

15、码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:1课程设计目标与任务11.1课程设计目标11. 2课程设计任务12分析与设计21.1 题目分析22. 2存储结构设计23. 3算法描述34. 4程序流程图45. 5算法实现说明43程序清单94测试125总结14参考文献151课程设计目标与任务1.1课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学 是软件设计的综合训练,包括问题分析，总体结构设计，用户界面设计，程序设 计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工 作方法学生通过数据结构课程设计各方面得到锻炼：(1)能

16、根据实际问题的具体情况结合数据结构课程中的基本理论和基本算 法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决 问题的有效算法；(2)通过上机实习，验证自己设计的算法的正确性，学会有效利用基本调试 方法，迅速找出程序代码中的错误并且修改；(3)培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进 一步提高程序设计水平；(4)尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来,将复杂的运行过程以动态方式显示出来，获得算法的直观感受。 1. 2课程设计任务实现树与二叉树的转换的实现，以及树的前序，后序的递归，非递归遍历算 法，层次序的非递归遍历

17、算法的实现，应包含建树的实现。(多种遍历算法只可 实现一个)利用本学期所学的数据结构的有关知识，实现树与二叉树相互转换，设计树 与二叉树转换的相关函数库，以便在程序设计中调用，要求：(1)实现树与二叉树的转换；(2)借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式 显示出来，将复杂的运行过程以动态方式显示出来；(3)给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。该课程设计通过实现树与二叉树的转换，理解树与二叉树的相互转化关系， 掌握树与二叉树的存储结构的异同，加深对二叉树和树的理解。2分析与设计2.1题目分析树的初始化函数（双亲法和孩子结点法两种），建树函数，输出

18、树函数，树 的前序遍历函数（递归和非递归两种），树的后序遍历函数（递归和非递归两种）， 树的层次遍历函数，一般树和二叉树的转换函数。2. 2存储结构设计分析树和二叉树的存储结构，二叉树的存储结构如图2.1o二叉树的存储结构链式存储结构图2. 1二叉树的存储结构图树是一种非线性的数据结构，树中的元素之间是一对多的层次关系。常用的 有三种存储结构，即双亲表示法、孩子表示法、和孩子兄弟表示法。事实上，一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树 的二叉链表存储结构是完全相同的，只是两个指针域的名称及解释不同而已通 过图直观的表示了树与二叉树之间的对应关系和相互转换方法。如图2.2o2.

19、 3算法描述一.二叉树创立：用链表实现创立一个树结点的结构体，从键盘输入数据， 存入数组。把下标 为2*i+l的值存入左孩子，为2*i+2的存入右孩子。二.先序遍历二叉树的递归算法：假设二叉树为空，那么空操作；否那么（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。三.后序遍历二叉树的递归算法：假设二叉树为空，那么空操作；否那么（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；四.先序非递归算法：BiNode根指针，假设BiNode!= NULL对于非递归算法, 引入栈模拟递归工作栈，初始时栈为空。五.后序非递归算法：BiNode是要遍历树的根指针，后序遍历要求在遍历

20、完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void F_PostOrder（BiNode root）六.层次序遍历算法：按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。2.4程序流程图该程序是先建立树，再以树为基础，将树转换成二叉树。该程序的流程是建 立树，利用队列，递归，指针等，将树的根结点变为二叉树的根结点，进行树到 二叉树的转换,程序的最终目的是根据输入的树的接点，孩子结点及其父亲结点, 生成二叉树，将树的先序遍历结果和二叉树的先序遍历的结果输出。如图2.3图2. 3程序流程图2. 5算法实现说明首先根据指令，输入信息，生成一个树后，再将生成的树转

21、化成二叉树，然 后输出二叉树的结构图,二叉树的前序遍历结果以及二叉树的深度和节点孩子数(1)输入关于树的结点后，遍历每个结点的操作就是输出该结点的data域, 首先先遍历树的根结点，再先序遍历树的孩子结点。void preorderTree(CTreeNode *ctroot)遍历每个结点的操作就是输出该结点 的data域CTreeNode *ctchild;int i;coutctroot-data;先遍历根结点for(i=0;ichildreni;if(ctchild=NULL)break;孩子结点遍历结束，退出elsepreorderTree(ctchild); 递归先序遍历)(2)定义

22、 BTreeNode*BTreeArrayMAX_NODE_NUM结构体指针数组，用于 存放结点的地址，开始初始化树队列，二叉树队列，并且分别将树和二叉树的元 素分别进行入队操作，在元素进入队列时要进行判断队列，看是否为满。然后再 把树队列元素出队，要进行队列是否为空的判断，利用指针返回结点的值，然后 进行二叉树队列元素出队，返回空指针后返回结点。该段程序的关键是元素的出 队入队操作。typedef struct nodeBTree(BTreeNode *BTreeArrayMAX_NODE_NUM;结构体指针数组，存放结点的地 址/struct nodeBTree *next;int BTr

23、eeFront,BTreeRear;QueueBTree;初始化树队列void initQueueCTree(QueueCTree *&q)(q=(QueueCTree *)malloc(sizeof(QueueCTree);q-CTreeFront=q-CTreeRear=0;初始化二叉树队列void initQueueBTree(QueueBTree *&q)(q=(QueueBTree *)malloc(sizeof(Q.ueueBTree);q-BTreeFront=q-BTreeRear=0;)int addQueueCTree(QueueCTree *&q,CTreeNode *c

24、troot)(if(q-CTreeRear+l)%MAX_NODE_NUM = q-CTreeFront) 队满return 0;q-CTreeRear=(q-CTreeRear+l)%MAX_NODE_NUM;q-CTreeArrayq-CTreeRear=ctroot;return 1;入队列)二叉树队列元素入队int addQueueBTree(QueueBTree *&q,BTreeNode *btroot)(if(q-BTreeRear+l)%MAX_NODE_NUM=q-BTreeFront)/IPBTreeRear=(q-BTreeRear+l)%MAX_NODE_NUM;q-BTreeArrayq-BTreeRear=btroot;return 1;入队列)(3)下面是树转换成二叉树的关键操作，树转换成二叉树时利用ctroot指 向树的根结点，利用btroot指向二叉树的根，增添一个辅助队列，并且增加开辟 内存空间的语句，并且树的根结点会作为二叉树的根结点，树的根结点入队后二 叉树的根结点入队，然后树结点出队，二叉树的结点出队，访问所有的孩子结点 后，分配二叉树的结点，按照树转换成二叉树的规那么，二叉树的左子树为树的左