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

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

1、河南工程学院数据结构与算法课程设计成果报告树与二叉树的转换实现2014年12月29日2.4程序流程图本程序开始后进入主菜单创立一棵树或退出程序，创立一棵一般树，那么进入 下一项先创立其结点，同时在每个结点中附设一个指针指示结点在链表中位置, 计算机会根据程序的流程输出树的结点情况，同时会输出一棵一般树创立完成的 具体情况，然后计算机会根据程序将这棵一般树转换成二叉树。然后输出树与二 叉树的先序遍历，见图2-3o主菜单创立一棵树输入树的信息树转化为二叉树树的先序遍历二叉树的先序遍历输出结果图2-3程序流程图3程序清单#include#include#define DEGREE 5 树的高度ttd

2、efine NULL 0#define QUEUESIZE 10#define MAX_NODE_NUM 100/树和二叉树的结构体/typedef struct stl树节点的类型(char data;数据域，采用char星struct stl *childrenDEGREE;指向孩子节点的指针域CTreeNode;typedef struct st2(char data;数据域struct st2 *lchild,*rchild;左右孩子节点的指针BTreeNode;CTreeNode *SearchCTree(CTreeNode *root ,char data)(int i;CTree

3、Node *returnNode;if(root-data=data)return root;else(for(i=0;ichildreni=NULL)return NULL;else(returnNode=SearchCTree(root-childreni,data); 递归查找 if(returnNode!=NULL)return returnNode;)CTreeNode *CreateSTree()int ij,k;char data, parent;CTreeNode *root,*parentNode,*node;printf(“请输入树的节点的数量:)；scanf(”d”,&j

4、);fflush(stdin); 清除键盘缓存if(j=O)return NULL;空树，结束函数print,请输入根节点的数据:)；scanf(%c，&data);fflush(stdin);root=(CTreeNode *)malloc(sizeof(CTreeNode);root-data=data;for(i=0;ichildreni=NULL;for(i=2;idata=data;for(k=0;kchildrenk=NULL;/printf(“验证 parent=%cn,parent);parentNode=SearchCTree(rootparent); 查找指定数据的节点 f

5、or(k=0;kchildrenk=NULL)(parentNode-childrenk=node;break;) return root;void preorderTree(CTreeNode *ctroot)遍历每个节点的操作就是输出该节点的data域(CTreeNode *ctchild;int i;printf(”%c，ctroot-data); 先遍历根节点for(i=0;ichildreni;if(ctchild=NULL)break;孩子节点遍历结束，退出elsepreorderTree(ctchild);递归先序遍历)typedef struct nodeCTree 树队列结构

6、体类型(CTreeNode *CTreeArrayMAX_NODE_NUM;结构体指针数组，存放节点的地址 struct nodeCTree *next;int CTreeFront,CTreeRear;QueueCTree;typedef struct nodeBTree二叉树队列结构类型(BTreeNode *BTreeArrayMAX_NODE_NUM;结构体指针数组，存放节点的地址 struct nodeBTree *next;int BTreeFront,BTreeRear;QueueBTree;void initQueueCTree(QueueCTree *&q)(q=(Queue

7、CTree *)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+l)%MAX_NODE_NUM=q-CTreeFront)/Mreturn 0;q-CTreeR

8、ear=(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)return 0;q-BTreeRear=(q-BTreeRear+l)%MAX_NODE_NUM;q-BT reeArrayq-BT reeRear=btroot;10return 1;入队列) int QueueCTreeEmpty

9、(QueueCTree *q)(return(q-CTreeFront=q-CTreeRear);/二叉树队列判空 int QueueBTreeEmpty(QueueBTree *q) (return(q-BTreeFront=q-BTreeRear);)CTreeNode *delQueueCTree(QueueCTree *&q) 树队列元素出队 (CTreeNode *ctroot;if(q-CTreeFront=q-CTreeRear)/|PCTreeFront=(q-CTreeFront+l)%MAX_NODE_NUM;ctroot=q-CTreeArrayq-CTreeFront;

10、return ctroot;返回节点二叉树队列元素出队BTreeNode *delQueueBTree(QueueBTree *&q) (BTreeNode *btroot;if(q-BTreeFront=q-BTreeRear)/K$return NULL;返回空指针q-BTreeFront=(q-BTreeFront+l)%MAX_NODE_NUM;btroot=q-BTreeArrayq-BTreeFront; return btroot;返回节点)树转化为二叉树void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)树转化为二叉树ct

11、root指向树的根节点，btroot,指向二叉树的跟 (QueueCTree *VisitedCTreeNodes;QueueBTree *VisitedBTreeNodes;辅助队歹U initQueueCTree(VisitedCTreeNodes);initQueueBTree(VisitedBTreeNodes);/初始化队歹 UCTreeNode *ctnode;BTreeNode *btnode,*p,*LastSibling;int i;btroot=(BTreeNode *)malloc(sizeof(BTreeNode);添力口开辟内存空间语句 btroot-data=ctr

12、oot-data; 树的根节点作为二叉树的根节点btroot-lchild=btroot-rchild=NULL;addQueueCTree(VisitedCTreeNodes,ctroot); addQueueBTree(VisitedBTreeNodes,btroot); 二叉树的总艮节 点入队11while(!QueueCTreeEmpty(VisitedCTreeNodes)(ctnode = delQueueCTree(VisitedCTreeNodes); 树节点出队btnode 二 delQueueBTree(VisitedBTreeNodes); 二叉树节点出队for(i=0;

13、ichildreni= NULL) 孩子节点访问完毕 break;p=(BTreeNode *)malloc(sizeof(BTreeNode);分配二叉树节点p-data=ctnode-childreni-data;p-lchild=p-rchild=NULL;if(i=0)btnodelchild二p; 长子，作为父节点的做孩子elseLastSibling-rchild=p; 作为上一个兄弟节点的右孩子 LastSibling=p;addQueueCTree(VisitedCTreeNodeS,Ctnodechildreni);/树节点进队歹U3|6101161168176(/15什61

14、8升061106|65市)；/二叉树节点进门队歹1|)void Preorder(BTreeNode *T)/ 二叉树的遍历if(printf(%2cH,T-data);Preorder(T-lchild);Preorder(T-rchild);)int main()主函数调用(CTreeNode *Tree;BTreeNode *BTree;printf(创立一棵树n);Tree=CreateSTree();printfC树的先序遍历结果为:)；preorderTree(Tree);printf(n);T reeT o BT ree(T ree,BT ree);print转换后的二叉树，先序

15、遍历的结果为门；Preorder(BTree);printf(n);return 0;124测试4.1测试数据创立一棵树，从键盘上输入树的基本信息，见图4-1。.E:DLllxlDebuglxl.exe.创立一啤松I懵输入树也重点曩数苇=6输入第2个节点的数据及其父节点的数据:BA 储输入第3个节点的数据及其父节点的数据:CAilLEpaient =A请的I入第4个节点的数据及其父节点的数据:DA ilTuaye nt =A请揄入第5个节点的数据及其父节点的数据:EB 正 pai*en 七=B请输入第6个节点的数据及其父节点的数据：FB图4-1树的基本信息图4. 2测试结果分析在输入树的基本信

16、息后，经过树与二叉树的转换后，输出树的先序遍历，再 输出二叉树的先序遍历。见图4-2。.E:DLllxlDebuglxl.exe建一军果树情揄入树的节点的数量;6情输入报节表的数瘤AP&i 正 pa*en 七=0廉输入第3个节点的数据及其父节点的数据C。P&i 正 pa*en 七=0廉输入第3个节点的数据及其父节点的数据C。懵输入第2个节点的数据及其父节点的数据:BA 情蒯入第4个节点的数据及其父节点的数据：DAPffcilTuai*ent =A请揄入第S个节点的数据及其父节点的数据:EB 5f&ijLEpaient =B博殉入第6个节点的数据及其父节点的数据:FB iilEpaient =B

17、Pi*ess any key to cont nue图4-2转换后的结果图135总结经过一周的数据结构上机实践学习，我在仔细阅读老师布置的任务之后，开 始查阅大量书本资料，并上网浏览的一些网络相关资源，有了充份的准备，开始 了上机实践编写程序，在实践过程中，有过许多疑惑和错误，但在老师的指导和 同学的帮助下，我耐心学习并改正了错误的地方，最终完成了老师布置的任务。 通过这次的上机实践学习，我收获许多，明白上课时只是认真听讲是不够的，要 在课余时多进行上机操作，这样才能更加深刻了解知识，才能掌握知识。上机实 践让我更加认识到自己的知识不全面，所以我以后要多加上机实践，巩固知识。14参考文献1严蔚

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

19、程设计源代码的排版总评成绩指导教师评语:日期:1课程设计目标与任务11.1课程设计目标11. 2课程设计任务11. 3课程设计要求12分析与设计21.1 题目分析22. 2存储结构设计22. 3算法描述42.4程序流程图73程序清单84测试134.1测试数据134. 2测试结果分析135总结14参考文献151课程设计目标与任务1.1课程设计目标通过课程设计，巩固所学的理论知识，培养综合运用所学知识解决实际问题 的能力。根据实际问题的具体情况，能设计出解决问题的有效算法。同时，在程 序设计方法及上机操作方面受到比拟系统严格的训练，培养软件工作所需要的动 手能力要求学生在设计中逐步提高程序设计能力

20、培养科学的软件工作方法学生 通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算 法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决 问题的有效算法；（2）通过上机实习，验证自己设计的算法的正确性，学会有效利用基本调试 方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进 一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来,将复杂的运行过程以动态方式显示出来，获得算法的直观感受。 1. 2课程设计任务结合数据结构所学知

21、识，掌握树与二叉树之间的转换关系，设计树与二叉 树转换的相关函数库，以便在程序设计中调用，完成以下功能：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1. 3课程设计要求根据提供的实习题目，认真完成软件设计的全部过程，并以最终软件设计成 果来证明其独立完成实际任务的能力，从而，反映出理解和运用数据结构与算法 的水平和能力，最后完成软件设计和程序调试并提交文档：课程设计报告书，报 告书中包含设计的算法及局部程序代码。2分析与设

22、计2.1题目分析本程序的功能是对任意树进行递归先序遍历，用队列实现对树与二叉树的转 换。本程序要求用户以字符输入，假设要实现终端结点，最后以回车键建入数据。 本程序的结果将依次打印出递归先序遍历，输出树及树转换成二叉树的先序遍 历。2. 2存储结构设计1、树的存储结构有多种，用二叉链表作树的存储结构，链表中每个结点的 两个指针域分别指向其第一个孩子结点和下一个兄弟结点。见图2-1 otypedef struct stl树节点的类型(char data;数据域struct stl *childrenDEGREE;指向孩子节点的指针域CTreeNode;2、二叉树的存储结构有两种，现用链式存储结构

23、作二叉树的存储结构，链 表中每个结点的两个指针域分别指向其左孩子结点和右孩子结点。见图2-1 otypedef struct st2二叉树节点的类型(char data;数据域struct st2 *lchild, *rchild;左右孩子节点的指针 BTreeNode;3、用队列来实现树用二叉链表存储时算法。typedef struct nodeCTree 树队列结构体类型(CTreeNode *CTreeArrayMAX_NODE_NUM;struct nodeCTree *next;int CTreeFront, CTreeRear;QueueCTree;图2-1树与二叉树存储结构图4、

24、二叉树用链式存储结构表示时，算法实现：（1）访问根结点，并将根结点入队；（2）当队列不空时，重复以下操作：从队列退出一个结点；假设其有左孩子, 那么访问左孩子，并将其左孩子入队；假设其有右孩子，那么访问右孩子，并将其右孩 子入队；typedef struct nodeBTree二叉树队列结构类型（BTreeNode *BTreeArray MAX_NODE_NUM; 结构体指针数组struct nodeBTree *next;int BTreeFront, BTreeRear;QueueBTree;2. 3算法描述1、创立一棵树并输入这棵树的基本信息，树的节点的数量，根节点的数据, 且依次输入

25、每个节点的信息。CTreeNode *CreateSTree()(int i, j, k;char data, parent;CTreeNode *root, *parentNode, *node;printf (请输入树的节点的数量:);scanf (d，&j);f flush (stdin);清除键盘缓存if (j=0)return NULL;空树，结束函数printf (请输入根节点的数据:)；scanf(%c, &data);fflush(stdin);root=(CTreeNode *)malloc(sizeof(CTreeNode);root-data=data;for (i=0;

26、iDEGREE;i+)root-chiIdreni=NULL;for (i=2; idata=data;for (k=O;kchi1drenk=NULL;/printf (验证 parent=%cnz，, parent);parentNode=SearchCTree(root, parent);for (k=0;kchildrenk=NULL)(parentNode-chiIdrenk=node;break;)return root; 42、将树转换成二叉树的步骤是：(1)加线。就是在所有兄弟结点之间加一条连线；(2)抹线。就是对树中的每个结点，只保存他与第一个孩子结点之间的连线，删除它与其它

27、孩子结点之间的连线；(3)旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度, 使之结构层次清楚。见图2-2。3、对树进行递归的先序遍历，先遍历根节点，再依次先序遍历孩子节点。 void preorderTree(CTreeNode *ctroot)(CTreeNode *ctchild;int i;printf (%c，ctroot-data);先遍历根节点for (i=0; iDEGREE; i+) 依次先序遍历孩子节点|ctchild=ctroot-childreni;if (ctchild=NULL)break;孩子节点遍历结束，退出elsepreorderTree(ctchild);递归先序遍历4、对二叉树的进行先序遍历，假设二叉树为空，那么操作结束，否那么依次执行如下3个操作：(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。void Preorder(BTreeNode *T)if (T)(printf (%2c, T-data);Preorder(T-lchiId);Preorder(T-rchiId);)