《数据结构课程设计树与二叉树的转换.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计树与二叉树的转换.docx（12页珍藏版）》请在三一办公上搜索。
1、数据结构课程设计报告设计题:_树与二叉树的转换.姓名：李锦 学号：211214011专业：物联网工 院系：计算机科学与技术 班级：1205指导教师：高秀梅2014年 2月 14日目录一、问题描述2二、基本要求2三、概要设计2四、数据结构设计2五、算法设计31、算法分析32、算法实现3六、程序测试与实现61、函数之间的调用关系62、主程序63、测试数据84、测试结果8七、调试分析10八、遇到的问题及解决办法10九、心得体会10一、问题描述完成树与二叉树的转换二、基本要求1、树采用双亲表示法2、能够将树转换为二叉树3、对转换的二叉树进行算法设计统计人一结点的孩子数4、利用转换的二叉树计算树的高度三
2、、概要设计操作集合：(1) CTreeNode *SearchCTree(CTreeNode *root ,char data)查找树结点(2) CTreeNode *CreateSTree() 生成树(3) void preorderTree(CTreeNode *ctroot) 树的遍历(4) void PrintTree(CTreeNode *troot,int depth) 树的输出(5 void initQueueCTree(QueueCTree *&q) 初始化树队列(6) void initQueueBTree(QueueBTree *&q) 初始化二叉树队列(7)void Tr
3、eeToBTree(CTreeNode *ctroot,BTreeNode *&btroot) /树转化为二叉树 ctroot 指向树的根节点，btroot,指向二叉树的根四、数据结构设计struct CTreeNode/树节点的类型(一char data;/数据域，采用 char 星struct CTreeNode *childrenDEGREE;/指向孩子节点的指针域 ;struct BTreeNodechar data;/数 据域BTreeNode *lchild,*rchild;/左右孩子节点的指针;树队列结构体类型struct QueueCTreeCTreeNode *CTreeAr
4、rayMAX_NODE_NUM;/结构体指针数组，存放节点的地址 /struct nodeCTree *next;int CTreeFront,CTreeRear;二叉树队列结构类型struct QueueBTreeBTreeNode *BTreeArrayMAX_NODE_NUM;/结构体指针数组，存放节点的地址 /struct nodeBTree *next;int BTreeFront,BTreeRear;五、算法设计1、算法分析将树转换成二叉树的步骤是：(1)加线。就是在所有兄弟结点之间加一条连线；(2) 抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子
5、 结点之间的连线；(3)旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度， 使之结构层次分明。2、算法实现void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)树转化为二叉树 ctroot 指向树的 根节点，btroot,指向二叉树的跟QueueCTree *VisitedCTreeNodes;QueueBTree *VisitedBTreeNodes;/辅助队列initQueueCTree(VisitedCTreeNodes);initQueueBTree(VisitedBTreeNodes);/初 始化队列CTreeNode *
6、ctnode;BTreeNode *btnode,*p,*LastSibling;int i;btroot=new BTreeNode;/添加开辟内存空间语句btroot-data=ctroot-data;/树的根节点作为二叉树的根节点btroot-lchild=btroot-rchild=NULL;addQueueCTree(VisitedCTreeNodes,ctroot);/树 的跟节点入队addQueueBTree(VisitedBTreeNodes,btroot);/二 叉树的跟节点入队while(!QueueCTreeEmpty(VisitedCTreeNodes)ctnode=d
7、elQueueCTree(VisitedCTreeNodes);/树节点出队 btnode=delQueueBTree(VisitedBTreeNodes);/二叉树节点出队 for(i=0;ichildreni=NULL)/孩 子节点访问完毕 break;p=new BTreeNode;/分 配二叉树节点 p-data=ctnode-childreni-data; p-lchild=p-rchild=NULL;if(i=0)btnode-lchild=p;/长子，作为父节点的做孩子elseLastSibling-rchild=p;/作上一 个兄弟节点的右孩子 LastSibling=p;ad
8、dQueueCTree(VisitedCTreeNodes,ctnode-childreni);/ 树节点进队列addQueueBTree(VisitedBTreeNodes,p);/二 叉树节点进门队列3、算法流程图六、程序测试与实现1、函数之间的调用关系2、主程序int main() CTreeNode *Tree;BTreeNode *BTree;int x=0;char n,i,j,k;while(1)p:n=menu();if(n=1)while(1)i=Treemenu();switch(i)case 1:Tree=CreateSTree();break;case 2:PrintT
9、ree(Tree,10);coutntt 按任意键返回.n”; getch();break;case 3:preorderTree(Tree);coutntt 按任意键返回.n”; getch();break;case 4:goto p;break;if(n=2)TreeToBTree(Tree,BTree);while(1)j=Btreemenu();switch(j)case 1:PrintIn(BTree,5);coutnt t 按任意键返回.n”; getch();break;case 2:Preorder(BTree);coutntt 按任意键返回.n”; getch();break
10、;case 3:coutFindDepth(BTree);coutntt 按任意键返回.n”; getch();break;case 4:count(BTree);coutntt 按任意键返回.n”;getch();break;case 5:goto p;break;if(n=3)break;return 0;3、测试数据a b c d e4、测试结果七、调试分析首先根据指令，输入信息，生成一个树后，再将生成的树转化成二叉树，然后输出二叉树的 结构图，二叉树的前序遍历结果以及二叉树的深度和节点孩子数八、遇到的问题及解决办法调试时遇到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时，容易进
11、入死循环， 经过查找资料、分步调试最终找到循环结束条件，顺利解决各个难题。九、心得体会通过本次课程设计，我发现，有关一个课题的所有知识不仅仅是在课本上，多查阅一些资料 能够更好的完成课题，这就需要一种能力，即自学能力。本次课程设计还让我认识到自己的 缺点。本次选的课题是二叉树的遍历，因为本学期所学的就是二叉树等数据结构，所以认为 比较适合。刚开始认为会很简单，但到后来就出现一些难以解决的问题，就像老师请教，并 查阅相关资料。经过慢慢的调试，最终测试成功。这次课程设计让我所学到的数据结构知 识发挥的淋漓尽致，而且还拓展了我的知识面，使我更加熟练的掌握各种方法。总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对数据结构更加了解。
