《数据结构》课程设计- -树与二叉树转换的实现.doc

河南工程学院数据结构与算法课程设计成果报告树与二叉树转换的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12 分析与设计32.1 题目分析32.2 存储结构设计32.3 算法描述42.4 程序流程图52.5 算法实现说明53 程序清单104 测试135 总结15参考文献161 课程设计目标与任务1.1 课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务实现树与二叉树的转换的实现，以及树的前序，后序的递归，非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。（多种遍历算法只可实现一个）利用本学期所学的数据结构的有关知识，实现树与二叉树相互转换，设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。该课程设计通过实现树与二叉树的转换，理解树与二叉树的相互转化关系，掌握树与二叉树的存储结构的异同，加深对二叉树和树的理解。2 分析与设计2.1 题目分析树的初始化函数（双亲法和孩子结点法两种），建树函数，输出树函数，树的前序遍历函数（递归和非递归两种），树的后序遍历函数(递归和非递归两种）,树的层次遍历函数，一般树和二叉树的转换函数。2.2 存储结构设计分析树和二叉树的存储结构，二叉树的存储结构如图2.1。 图2.1二叉树的存储结构图树是一种非线性的数据结构，树中的元素之间是一对多的层次关系。常用的有三种存储结构，即双亲表示法、孩子表示法、和孩子兄弟表示法。 事实上，一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的，只是两个指针域的名称及解释不同而已,通过图直观的表示了树与二叉树之间的对应关系和相互转换方法。如图2.2。图2.2 树和二叉树的转换图2.3 算法描述一.二叉树创建: 用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标 为2*i+1 的值存入左孩子，为2*i+2的存入右孩子。二. 先序遍历二叉树的递归算法: 若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。三.后序遍历二叉树的递归算法: 若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点； 四. 先序非递归算法: BiNode根指针，若 BiNode!= NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。五. 后序非递归算法: BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void F_PostOrder(BiNode root)六. 层次序遍历算法：按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。2.4 程序流程图该程序是先建立树，再以树为基础，将树转换成二叉树。该程序的流程是建立树，利用队列，递归，指针等，将树的根结点变为二叉树的根结点，进行树到二叉树的转换，程序的最终目的是根据输入的树的接点，孩子结点及其父亲结点，生成二叉树，将树的先序遍历结果和二叉树的先序遍历的结果输出。如图2.3主菜单树的信息图二叉树的信息图输入信息生成树输入树的结点数输入孩子结点及其父亲结点输出树的前序遍历输出二叉树的前序遍历图2.3程序流程图2.5 算法实现说明首先根据指令，输入信息，生成一个树后，再将生成的树转化成二叉树，然后输出二叉树的结构图,二叉树的前序遍历结果以及二叉树的深度和节点孩子数（1）输入关于树的结点后，遍历每个结点的操作就是输出该结点的data域,首先先遍历树的根结点，再先序遍历树的孩子结点。void preorderTree(CTreeNode *ctroot)/遍历每个结点的操作就是输出该结点的data域 CTreeNode *ctchild; int i; coutdata ;/先遍历根结点 for(i=0;ichildreni; if(ctchild=NULL) break;/孩子结点遍历结束，退出 else preorderTree(ctchild);/递归先序遍历（2）定义BTreeNode *BTreeArrayMAX_NODE_NUM结构体指针数组，用于存放结点的地址，开始初始化树队列，二叉树队列，并且分别将树和二叉树的元素分别进行入队操作，在元素进入队列时要进行判断队列，看是否为满。然后再把树队列元素出队，要进行队列是否为空的判断，利用指针返回结点的值，然后进行二叉树队列元素出队，返回空指针后返回结点。该段程序的关键是元素的出队入队操作。typedef struct nodeBTreeBTreeNode *BTreeArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址/struct nodeBTree *next;int BTreeFront,BTreeRear;QueueBTree;/初始化树队列void initQueueCTree(QueueCTree *&q) q=(QueueCTree *)malloc(sizeof(QueueCTree); q-CTreeFront=q-CTreeRear=0;/初始化二叉树队列void initQueueBTree(QueueBTree *&q) q=(QueueBTree *)malloc(sizeof(QueueBTree); q-BTreeFront=q-BTreeRear=0;int addQueueCTree(QueueCTree *&q,CTreeNode *ctroot) if(q-CTreeRear+1)%MAX_NODE_NUM=q-CTreeFront)/队满 return 0; q-CTreeRear=(q-CTreeRear+1)%MAX_NODE_NUM; q-CTreeArrayq-CTreeRear=ctroot; return 1;/入队列/二叉树队列元素入队int addQueueBTree(QueueBTree *&q,BTreeNode *btroot) if(q-BTreeRear+1)%MAX_NODE_NUM=q-BTreeFront)/队满 return 0; q-BTreeRear=(q-BTreeRear+1)%MAX_NODE_NUM; q-BTreeArrayq-BTreeRear=btroot; return 1;/入队列（3）下面是树转换成二叉树的关键操作，树转换成二叉树时利用ctroot指向树的根结点，利用btroot指向二叉树的根，增添一个辅助队列，并且增加开辟内存空间的语句，并且树的根结点会作为二叉树的根结点，树的根结点入队后二叉树的根结点入队，然后树结点出队，二叉树的结点出队，访问所有的孩子结点后，分配二叉树的结点，按照树转换成二叉树的规则，二叉树的左子树为树的左子树，从根开始一直向右，遇到的右子树均依次作为树的子树(二叉树中结点的右子树中变为该结点右侧的兄弟），将树转化成二叉树。void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/树转化为二叉树ctroot指向树的根结点，btroot,指向二叉树的根 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes;/辅助队列 initQueueCTree(VisitedCTreeNodes); initQueueBTree(VisitedBTreeNodes);/初始化队列 CTreeNode *ctnode; BTreeNode *btnode,*p,*LastSibling; int i; btroot=(BTreeNode *)malloc(sizeof(BTreeNode);/添加开辟内存空间语句 btroot-data=ctroot-data;/树的根结点作为二叉树的根结点 btroot-lchild=btroot-rchild=NULL; addQueueCTree(VisitedCTreeNodes,ctroot);/树的根结点入队 addQueueBTree(VisitedBTreeNodes,btroot);/二叉树的根结点入队 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(i=0) btnode-lchild=p;/长子，作为父结点的做孩子 else LastSibling-rchild=p;/作为上一个兄弟结点的右孩子 LastSibling=p;addQueueCTree(VisitedCTreeNodes,ctnode-childreni);/树结点进队列 addQueueBTree(VisitedBTreeNodes,p);/二叉树结点进门队列void Preorder(BTreeNode *T) if(T) coutdatalchild); Preorder(T-rchild); 3 程序清单/初始化树(双亲表示法)voidinit_ptree(PTree*tree)tree-count=-1;/初始化树结点(孩子兄弟表示法)BTNodeGetTreeNode(intx)BTNodet;t.data=x;t.firstchild=t.rightsib=NULL;returnt;/树的前序遍历(递归)voidpreorder(BTNode*T)if(T!=NULL)printf(%d,T-data);preorder(T-firstchild);preorder(T-rightsib);/树的前序遍历(非递归)voidpreorder2(PTreeT)inti,j=0;BTNodepMAX_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=1;idata)j+;is=&pj;if(!(is-firstchild)is-firstchild=ip;ir=ip;elseir-rightsib=ip;ir=ip;Tree=&p0;returnTree;/*主菜单*/voidMenu() printf(=主菜单=n); printf(*输入1-以双亲法创建一棵一般树*n); printf(*输入2-树的前序遍历(递归)*n); printf(*输入3-树的后序遍历(递归)*n); printf(*输入4-树的前序遍历(非递归)*n); printf(*输入5-树的后序遍历(非递归)*n); printf(*输入6-层次序的非递归遍历*n); printf(*输入0-退出程序*n); printf(=n);printf(请输入执行的指令:);/*副菜单*/voidMenu2()printf(*副菜单*n);printf(*9-返回主菜单继续操作*n);printf(*0-退出程序*n);/*主函数*/voidmain()inti=0,c1,c2;PTreeT;BTNode*Tree;init_ptree(&T);loop:Menu();scanf(%d,&c1);switch(c1)case1:printf(建立一般树,依次输入各个结点情况:n);printf(输入结点方式:双亲数据,整型数据(第一个结点双亲数据为-1,最后以-1,-1结束)n例子:-1,11,3n);T=CreatTree(T);Tree=change(T);printf(一般树转换成二叉树后的情况:n);PrintBTree(Tree,i);getchar();break;case2:printf(树的前序遍历(递归):n);preorder(Tree);printf(n);break;case3:printf(树的后序遍历(递归):n);inoeder(Tree);printf(n);break;case4:printf(树的前序遍历(非递归):n);preorder2(T);printf(n); break;case5:printf(树的后序遍历(非递归):n);inoeder2(T);printf(n);break;case6:printf(树的层次遍历:n);level(T);printf(n);break;case0:exit(1); break;Menu2();scanf(%d,&c2);if(c2=9)gotoloop;elseif(c2=0)exit(1);4 测试输入执行的命令之后得到树的层次遍历。如图4.1 图4.1树的层次遍历输入执行的命令之后得到 树的前序遍历。如图4.2图4.2树的前序遍历输入执行的命令之后得到树的后序遍历。如图4.3图4.3树的后序遍历5 总结通过本次课程设计，我明白了有关一个课题的所有知识不仅是在课本上，而且还要多查阅一些资料才能够更好的完成课题，这就需要一种能力，即自学能力。本次课程设计还让我认识到自己的缺点。我选的是设计树与二叉树转换的相关函数库，刚开始认为会很简单，但到后来就出现一些难以解决的问题，就向同学请教，并查阅相关资料。经过慢慢的调试，最终测试成功。这次课程设计让我所学到的数据结构知识发挥的淋漓尽致，而且还拓展了我的知识面，使我更加熟练的掌握各种方法。总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对数据结构更加了解。参考文献1数据结构（C语言版）严蔚敏 清华大学出版社 20022数据结构-C语言描述 王路群 中国水利水电出版社 20073. 数据结构实验教程（C语言版） 王国钧 清华大学出版社 20094数据结构题集严蔚敏,吴伟民编 清华大学出版社 2002/初始化树(双亲表示法) void init_ptree(PTree *tree) tree-count=-1; /初始化树结点(孩子兄弟表示法) 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 pMAX_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=1;idata) j+; is=&pj; if(!(is-firstchild) is-firstchild=ip; ir=ip; else ir-rightsib=ip; ir=ip; Tree=&p0; return Tree; /*主菜单*/ void Menu() printf(=主菜单=n); printf(*输入1-以双亲法创建一棵一般树*n); printf(*输入2-树的前序遍历(递归)*n); printf(*输入3-树的后序遍历(递归)*n); printf(*输入4-树的前序遍历(非递归)*n); printf(*输入5-树的后序遍历(非递归)*n); printf(*输入6