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

学习资料收集于网络，仅供参考数据结构课程设计报告 设计题目：_树与二叉树的转换_ 姓名：_李锦_ 学号：_211214011_ 专业：_物联网工程_ 院系：_计算机科学与技术_ 班级：_1205_ 指导教师：_高秀梅_2014年 2 月 14 日 目 录一、问题描述2二、基本要求2三、概要设计2四、数据结构设计2五、算法设计31、算法分析32、算法实现3六、程序测试与实现61、函数之间的调用关系62、主程序63、测试数据84、测试结果8七、调试分析10八、遇到的问题及解决办法10九、心得体会10一、问题描述完成树与二叉树的转换二、基本要求1、 树采用双亲表示法2、 能够将树转换为二叉树3、 对转换的二叉树进行算法设计统计人一结点的孩子数4、 利用转换的二叉树计算树的高度三、概要设计操作集合：(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 TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot) /树转化为二叉树ctroot指向树的根节点，btroot,指向二叉树的根四、数据结构设计struct CTreeNode/树节点的类型 char data;/数据域，采用char星 struct CTreeNode *childrenDEGREE;/指向孩子节点的指针域;struct BTreeNode char data;/数据域 BTreeNode *lchild,*rchild;/左右孩子节点的指针;/树队列结构体类型struct QueueCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/结构体指针数组，存放节点的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear;/二叉树队列结构类型struct QueueBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/结构体指针数组，存放节点的地址 /struct nodeBTree *next; int BTreeFront,BTreeRear;五、算法设计 1、算法分析 将树转换成二叉树的步骤是： （1）加线。就是在所有兄弟结点之间加一条连线； （2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线； （3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。2、算法实现void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/树转化为二叉树ctroot指向树的根节点，btroot,指向二叉树的跟 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes;/辅助队列 initQueueCTree(VisitedCTreeNodes); initQueueBTree(VisitedBTreeNodes);/初始化队列 CTreeNode *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=delQueueCTree(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;/长子，作为父节点的做孩子 else LastSibling-rchild=p;/作为上一个兄弟节点的右孩子 LastSibling=p; addQueueCTree(VisitedCTreeNodes,ctnode-childreni);/树节点进队列 addQueueBTree(VisitedBTreeNodes,p);/二叉树节点进门队列 3、算法流程图开始主菜单输入树的节点数输入信息生成树输入树的节点数树转化为二叉树树的信息图二叉树的信息图树的前序遍历树的结构图二叉树的节点孩子数二叉树的深度二叉树的前序遍历二叉树的结构图输出结果退出程序六、程序测试与实现1、函数之间的调用关系Main()Menu()PrintTree(Tree,10)preorderTree(Tree)CTreeNode *Tree;TreeToBTree(Tree,BTree)Preorder(BTree)PrintIn(BTree,5)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:PrintTree(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);coutntt按任意键返回.n; getch();break; case 2:Preorder(BTree);coutntt按任意键返回.n; getch();break; 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 e 4、测试结果七、调试分析首先根据指令，输入信息，生成一个树后，再将生成的树转化成二叉树，然后输出二叉树的结构图,二叉树的前序遍历结果以及二叉树的深度和节点孩子数八、遇到的问题及解决办法调试时遇到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时，容易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利解决各个难题。九、心得体会通过本次课程设计，我发现，有关一个课题的所有知识不仅仅是在课本上，多查阅一些资料能够更好的完成课题，这就需要一种能力，即自学能力。本次课程设计还让我认识到自己的缺点。本次选的课题是二叉树的遍历，因