2021年数据结构课程设计树与二叉树的转换.doc

《数据结构》课程设计汇报设计题目:_树和二叉树转换___姓名:_______李锦_____________学号:_______________专业:_______物联网工程_______ 院系:_______计算机科学和技术_______班级:__________1205___________指导老师:_________高秀梅______2月14日目录一、问题描述 2二、基础要求 2三、概要设计 2四、数据结构设计 2五、算法设计 31、算法分析 32、算法实现 3六、程序测试和实现 61、函数之间调用关系 62、主程序 63、测试数据 84、测试结果 8七、调试分析 10八、碰到问题及处理措施 10九、心得体会 10一、问题描述完成树和二叉树转换二、基础要求树采取双亲表示法能够将树转换为二叉树对转换二叉树进行算法设计统计人一结点孩子数利用转换二叉树计算树高度三、概要设计操作集合:(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;//左右孩子节点指针};//树队列结构体类型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);//二叉树跟节点入队while(!QueueCTreeEmpty(VisitedCTreeNodes)){ctnode=delQueueCTree(VisitedCTreeNodes);//树节点出队btnode=delQueueBTree(VisitedBTreeNodes);//二叉树节点出队for(i=0;i<DEGREE;i++)//访问节点全部孩子节点{if(ctnode->children[i]==NULL)//孩子节点访问完成b