数据结构课程设计树与二叉树的转换.docx
- 文档编号:15960441
- 上传时间:2023-07-09
- 格式:DOCX
- 页数:12
- 大小:233.22KB
数据结构课程设计树与二叉树的转换.docx
《数据结构课程设计树与二叉树的转换.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计树与二叉树的转换.docx(12页珍藏版)》请在冰点文库上搜索。
数据结构课程设计树与二叉树的转换
《数据结构》课程设计报告
设计题目:
_树与二叉树的转换___
姓名:
_______李锦_____________
学号:
________211214011_______
专业:
_______物联网工程_______
院系:
_______计算机科学与技术_______
班级:
__________1205___________
指导教师:
_________高秀梅______
2014年2月14日
一、问题描述2
二、基本要求2
三、概要设计2
四、数据结构设计2
五、算法设计3
1、算法分析3
2、算法实现3
六、程序测试与实现6
1、函数之间的调用关系6
2、主程序6
3、测试数据8
4、测试结果8
七、调试分析10
八、遇到的问题及解决办法10
九、心得体会10
一、问题描述
完成树与二叉树的转换
二、基本要求
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;//左右孩子节点的指针
};
//树队列结构体类型
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 { 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;//长子,作为父节点的做孩子 else LastSibling->rchild=p;//作为上一个兄弟节点的右孩子 LastSibling=p; addQueueCTree(VisitedCTreeNodes,ctnode->children[i]);//树节点进队列 addQueueBTree(VisitedBTreeNodes,p);//二叉树节点进门队列 } 3、算法流程图 六、程序测试与实现 1、函数之间的调用关系 2、主程序 intmain() { CTreeNode*Tree; BTreeNode*BTree; intx=0; charn,i,j,k; while (1) { p: n=menu(); if(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': cout< getch();break; case'4': count(BTree);cout<<"\n\t\t按任意键返回...\n"; getch();break; case'5': gotop;break; } } } if(n=='3') { break; } } return0; } 3、测试数据 abcde 4、测试结果 七、调试分析 首先根据指令,输入信息,生成一个树后,再将生成的树转化成二叉树,然后输出二叉树的结构图,二叉树的前序遍历结果以及二叉树的深度和节点孩子数 八、遇到的问题及解决办法 调试时遇到诸多问题,其中最主要的问题是死循环问题,在非递归遍历时,容易进入死循环,经过查找资料、分步调试最终找到循环结束条件,顺利解决各个难题。 九、心得体会 通过本次课程设计,我发现,有关一个课题的所有知识不仅仅是在课本上,多查阅一些资料能够更好的完成课题,这就需要一种能力,即自学能力。 本次课程设计还让我认识到自己的缺点。 本次选的课题是二叉树的遍历,因为本学期所学的就是二叉树等数据结构,所以认为比较适合。 刚开始认为会很简单,但到后来就出现一些难以解决的问题,就像老师请教,并查阅相关资料。 经过慢慢的调试,最终测试成功。 这次课程设计让我所学到的数据结构知识发挥的淋漓尽致,而且还拓展了我的知识面,使我更加熟练的掌握各种方法。 总之,这次课程设计增强了我的自学能力,拓展了我的知识面,让我对数据结构更加了解。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 二叉 转换
![提示](https://static.bingdoc.com/images/bang_tan.gif)