数据结构课程设计树与二叉树的转换

数据结构课程设计0《数据结构》课程设计报告设计题目：_树与二叉树的转换___姓名：_______李锦_____________学号：________211214011_______专业：_______物联网工程_______院系：_______计算机科学与技术_______班级：__________1205___________指导教师：_________高秀梅______2014年2月14日数据结构课程设计1目录一、问题描述................................................................................................................2二、基本要求................................................................................................................2三、概要设计................................................................................................................2四、数据结构设计........................................................................................................2五、算法设计................................................................................................................31、算法分析.............................................................................................................................32、算法实现.............................................................................................................................3六、程序测试与实现....................................................................................................61、函数之间的调用关系.........................................................................................................62、主程序.................................................................................................................................63、测试数据.............................................................................................................................84、测试结果.............................................................................................................................8七、调试分析..............................................................................................................10八、遇到的问题及解决办法......................................................................................10九、心得体会..............................................................................................................10数据结构课程设计2一、问题描述完成树与二叉树的转换二、基本要求1、树采用双亲表示法2、能够将树转换为二叉树3、对转换的二叉树进行算法设计统计人一结点的孩子数4、利用转换的二叉树计算树的高度三、概要设计操作集合：(1)CTreeNode*SearchCTree(CTreeNode*root,chardata)查找树结点(2)CTreeNode*CreateSTree()生成树(3)voidpreorderTree(CTreeNode*ctroot)树的遍历(4)voidPrintTree(CTreeNode*troot,intdepth)树的输出(5voidinitQueueCTree(QueueCTree*&q)初始化树队列(6)voidinitQueueBTree(QueueBTree*&q)初始化二叉树队列（7）voidTreeToBTree(CTreeNode*ctroot,BTreeNode*&btroot)//树转化为二叉树ctroot指向树的根节点，btroot,指向二叉树的根四、数据结构设计structCTreeNode//树节点的类型{chardata;//数据域，采用char星structCTreeNode*children[DEGREE];//指向孩子节点的指针域};structBTreeNode{chardata;//数据域BTreeNode*lchild,*rchild;//左右孩子节点的指针};数据结构课程设计3//树队列结构体类型structQueueCTree{CTreeNode*CTreeArray[MAX_NODE_NUM];//结构体指针数组，存放节点的地址//structnodeCTree*next;intCTreeFront,CTreeRear;};//二叉树队列结构类型structQueueBTree{BTreeNode*BTreeArray[MAX_NODE_NUM];//结构体指针数组，存放节点的地址//structnodeBTree*next;intBTreeFront,BTreeRear;};五、算法设计1、算法分析将树转换成二叉树的步骤是：（1）加线。就是在所有兄弟结点之间加一条连线；（2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；（3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。2、算法实现voidTreeToBTree(CTreeNode*ctroot,BTreeNode*&btroot)//树转化为二叉树ctroot指向树的根节点，btroot,指向二叉树的跟{QueueCTree*VisitedCTreeNodes;QueueBTree*VisitedBTreeNodes;//辅助队列initQueueCTree(VisitedCTreeNodes);initQueueBTree(VisitedBTreeNodes);//初始化队列CTreeNode*ctnode;BTreeNode*btnode,*p,*LastSibling;inti;btroot=newBTreeNode;//添加开辟内存空间语句btroot-data=ctroot-data;//树的根节点作为二叉树的根节点btroot-lchild=btroot-rchild=NULL;addQueueCTree(VisitedCTreeNodes,ctroot);//树的跟节点入队addQueueBTree(VisitedBTreeNodes,btroot);//二叉树的跟节点入队数据结构课程设计4while(!QueueCTreeEmpty(VisitedCTreeNodes)){ctnode=delQueueCTree(VisitedCTreeNodes);//树节点出队btnode=delQueueBTree(VisitedBTreeNodes);//二叉树节点出队for(i=0;iDEGREE;i++)//访问节点所有的孩子节点{if(ctnode-children[i]==NULL)//孩子节点访问完毕break;p=newBTreeNode;//分配二叉树节点p-data=ctnode-children[i]-data;p-lchild=p-rchild=NULL;if(i==0)btnode-lchild=p;//长子，作为父节点的做孩子elseLastSibling-rchild=p;//作为上一个兄弟节点的右孩子LastSibling=p;addQueueCTree(VisitedCTreeNodes,ctnode-children[i]);//树节点进队列addQueueBTree(VisitedBTreeNodes,p);//二叉树节点进门队列}3、算法流程图数据结构课程设计5开始主菜单树的信息图二叉树的信息图输入信息生成树树的结构图树的前序遍历二叉树的结构图二叉树的前序遍历二叉树的深度二叉树的节点孩子数树转化为二叉树输入树的节点数输入树的节点数输出结果退出程序数据结构课程设计6六、程序测试与实现1、函数之间的调用关系2、主程序intmain(){CTreeNode*Tree;BTreeNode*BTree;intx=0;charn,i,j,k;while(1){p:n=menu();Main()Menu()CTreeNode*Tree;TreeToBTree(Tree,BTree)Preorder(BTree)preorderTree(Tree)PrintTree(Tree,10)PrintIn(BTree,5)数据结构课程设计7if(n=='1'){while(1){i=Treemenu();switch(i){case'1':Tree=CreateSTree();break;case'2':PrintTree(Tree,10);cout\n\t\t按任意键返回...\n;getch();break;case'3':preorderTree(Tree);cout\n\t\t按任意键返回...\n;getch();break;case'4':gotop;break;}}}if(n=='2'){TreeToBTree(Tree,BTree);while(1){j=Btreemenu();switch(j){case'1':PrintIn(BTree,5);cout\n\t\t按任意键返回...\n;getch();break;case'2':Preorder(BTree);cout\n\t\t按任意键返回...\n;getch();break;case'3':coutFindDepth(BTree);cout\n\t\t按任意键返回...\n;getch();break;case'4':count(BTree);cout\n\t\t按任意键返回...\n;getch();break;case'5':gotop;break;}}}if(n=='3'){break