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

《数据结构课程设计树与二叉树的转换》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计《数据结构》课程设计报告设计题目：_树与二叉树的转换___姓名：_______李锦_____________学号：________211214011_______专业：_______物联网工程_______院系：_______计算机科学与技术_______班级：__________1205___________指导教师：_________高秀梅______2014年2月14日10数据结构课程设计目录一、问题描述2二、基本要求2三、概要设计2四、数据结构设计2五、算法设计31、算法分析32、算法实现3六、程序测试与实现61、函数之间的

2、调用关系62、主程序63、测试数据84、测试结果8七、调试分析10八、遇到的问题及解决办法10九、心得体会1010数据结构课程设计一、问题描述完成树与二叉树的转换二、基本要求1、树采用双亲表示法2、能够将树转换为二叉树3、对转换的二叉树进行算法设计统计人一结点的孩子数4、利用转换的二叉树计算树的高度三、概要设计操作集合：(1)CTreeNode*SearchCTree(CTreeNode*root,chardata)查找树结点(2)CTreeNode*CreateSTree()生成树(3)voidpreorderTree(CTreeNode*ctr

3、oot)树的遍历(4)voidPrintTree(CTreeNode*troot,intdepth)树的输出(5voidinitQueueCTree(QueueCTree*&q)初始化树队列(6)voidinitQueueBTree(QueueBTree*&q)初始化二叉树队列（7）voidTreeToBTree(CTreeNode*ctroot,BTreeNode*&btroot)//树转化为二叉树ctroot指向树的根节点，btroot,指向二叉树的根四、数据结构设计structCTreeNode//树节点的类型{chardata;//数据域，

4、采用char星structCTreeNode*children[DEGREE];//指向孩子节点的指针域};structBTreeNode{chardata;//数据域BTreeNode*lchild,*rchild;//左右孩子节点的指针};10数据结构课程设计//树队列结构体类型structQueueCTree{CTreeNode*CTreeArray[MAX_NODE_NUM];//结构体指针数组，存放节点的地址//structnodeCTree*next;intCTreeFront,CTreeRear;};//二叉树队列结构类型struct

5、QueueBTree{BTreeNode*BTreeArray[MAX_NODE_NUM];//结构体指针数组，存放节点的地址//structnodeBTree*next;intBTreeFront,BTreeRear;};五、算法设计1、算法分析将树转换成二叉树的步骤是：（1）加线。就是在所有兄弟结点之间加一条连线；（2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；（3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。2、算法实现voidTreeToBTree(CTr

6、eeNode*ctroot,BTreeNode*&btroot)//树转化为二叉树ctroot指向树的根节点，btroot,指向二叉树的跟{QueueCTree*VisitedCTreeNodes;QueueBTree*VisitedBTreeNodes;//辅助队列initQueueCTree(VisitedCTreeNodes);initQueueBTree(VisitedBTreeNodes);//初始化队列CTreeNode*ctnode;BTreeNode*btnode,*p,*LastSibling;inti;btroot=newBTr

7、eeNode;//添加开辟内存空间语句btroot->data=ctroot->data;//树的根节点作为二叉树的根节点btroot->lchild=btroot->rchild=NULL;addQueueCTree(VisitedCTreeNodes,ctroot);//树的跟节点入队addQueueBTree(VisitedBTreeNodes,btroot);//二叉树的跟节点入队10数据结构课程设计while(!QueueCTreeEmpty(VisitedCTreeNodes)){ctnode=delQueueCTree(Visited

8、CTreeNodes);//树节点出队btnode=delQueueBTree(VisitedBTreeNodes);//