树的应用.doc

。青岛理工大学数据结构课程设计报告题目： 树的应用 院（系）： 计算机工程学院 学生姓名: 管巨伟 班级： 软件132 学号: 201307227起迄日期: 7.13-7.24指导教师: 李传斌 杨鑫 -可编辑修改-任务书一、数据结构课程设计的目标课程设计是数据结构课程的一个重要的实践环节，它可加深学生对该课程所学内容的进一步的理解与巩固，达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，培养基本的对基本数据结构的理解和运用，良好的程序设计方法、提高编码及调试程序技能的能力，为整个专业的学习以及软件设计水平的提高打下良好的基础。二、设计内容及要求【问题描述】（1） 要求实现树与二叉树的转换；（2） 树的先序、后序的递归、非递归算法，层次序的非递归算法的实现；（3） 在树中进行查找、插入（新插入的结点以叶子的形式插入树中）和删除的运算。【设计要求】遍历内容可以是数值可以是字符或者记录等等。一、需求分析 1.问题描述：该课题要求自己了解树的基本应用，能够使用先序遍历、后序遍历、层次遍历来遍历树的结点。掌握递归方法与非递归方法对树的操作。能够操作树，在树中进行插入、删除、查找等操作。熟练掌握树与二叉树的对应关系，在两者间进行熟练转化。这就使整个程序需要用递归及非递归方法进行树的先序、后序、层次遍历，能在树中插入、删除叶子结点，同时进行任意结点的查找，同时将树与二叉树进行转换。 2.基本功能 1、 通过用户的输入创建一棵树；2、 先序递归遍历整棵树；3、 先序非递归遍历整棵树；4、 后序递归遍历整棵树；5、 后序非递归遍历整棵树；6、 层次非递归遍历整棵树；7、 将树转换为二叉树；8、 查找、删除、插入用户输入的对应元素。二、 概要设计1.设计思路：树的建立过程采用子节点与父节点关联方法，寻找父节点，将子节点放入父节点的指针域，依次循环建立，完成建树过程。先序遍历的递归方法每次遍历到一个节点即输出节点的数据，依次调用遍历函数即可。先序非递归遍历过程用数组存储节点，每当存入一个节点即判断节点的孩子是否为空，为空停止采用标记位置返回父节点，遍历父节点的其他孩子，不为空时继续遍历该节点的孩子，直到孩子节点为空的节点。后序遍历递归类似先序遍历递归，此时输出节点数据域放在最后，而不是遍历递归之前。后序遍历非递归，建立一个栈，存入根节点，开始循环存入节点的孩子，存完孩子节点此时栈顶节点出栈，并给予标记，如有孩子节点遍历该节点的孩子节点存入栈中，如果没有，输出当前节点的数据域，依次循环即可。层次遍历过程定义数组，遍历节点的所有孩子节点存入，数组下标加一，遍历此时下标对应的节点的所有孩子节点存入数组，依次重复循环，最后输出数组中元素。树转化为二叉树过程，将树根结点存入树队列，出队，遍历到的第一个孩子节点放在二叉树根节点的左边，之后的孩子节点放在第一个孩子节点的右边，树队列节点再次出队，如此循环。插入时采用先序遍历方式查找到父节点，创建节点存储输入的元素，将该新节点放入找到的节点指针域即可。删除过程，遍历节点的孩子，当一个节点的其中一个孩子数据符合删除的节点，并且该节点的孩子为空，将节点的指针域置为空，并释放待删除节点的空间。查找采用先序遍历，找到后输出先序遍历的节点位置。 2.数据结构设计：ADT Tree数据对象D：D是具有相同特性的数据元素的集合。数据关系：若D为空集，则称树为空树；若D仅含一个数据元素，则称R为空集，否则R=H，H是如下二元关系：（1） 在D中存放唯一的称为根的数据元素root，它在关系H下无前驱；（2） 若D-root！=Q，则存在D-root的一个划分D1，D2，D3，.Dm(m0),对任意j！=k（1=j,k=m）有D1Dk=Q，且对任意的i（1=i=m），唯一存在数据元素xiDi,有H；（3） 对应于D-root的划分，H-,.有唯一的一个划分H1,H2.,Hm(m0),对任意j！=k（1=j,k=m）有HjHk=Q，且对任意i（1=idata=data; for(i=0;ichildreni=NULL; for(i=2;idata=data; for(k=0;kchildrenk=NULL;parentNode=SearchCTree(root,parent);/查找指定数据的节点 for(k=0;kchildrenk=NULL) parentNode-childrenk=node; break; return root;先序递归遍历：void preorderTree(CTreeNode *ctroot)/先序遍历递归算法 CTreeNode *ctchild; int i;if(ctroot=NULL)return;printf(%c,ctroot-data);/先遍历根节点 for(i=0;ichildreni; if(ctchild=NULL) continue;/孩子节点遍历结束，退出 else preorderTree(ctchild);/递归先序遍历 先序非递归遍历：void preorderTree(CTreeNode *ctroot)/先序遍历非递归算法 CTreeNode *queueNODENUM,*p; int rear=0,front=0,mark;/mark作为指针往前一个节点跳的标志 queuerear=ctroot; if(ctroot=NULL) return; if(queuerear-children0=NULL)/只有根节点的树 return; p=queuerear;FOR:for(int i=0;ichildreni; if(p=NULL) break;/孩子节点遍历结束，退出 elsequeue+rear=p-childreni;p=queuerear;goto FOR; while(front=rear)Visit(data);后序递归遍历：void lastorderTree(CTreeNode *ctroot)/后序遍历递归算法if(ctroot=NULL)return;CTreeNode *ctchild; int i;for(i=0;ichildreni; if(ctchild=NULL) continue;/孩子节点遍历结束，退出 else lastorderTree(ctchild);/递归后序遍历Visit（data）;后序非递归遍历：void lastnorderTree(CTreeNode *ctroot)/后序遍历非递归算法if(ctroot=NULL)return; int k; CTreeNode *stackNODENUM,*p; int markNODENUM,i; int top = -1; stack+top =ctroot;/根节点入栈 marktop = 0; while(top=0)/栈中有节点 p = stacktop; for(i=0;ichildreni!=NULL)/当子树不为空，并且未执行过入栈操作 marktop = 1;for(k=CHILD-1;k=0;k-)/从最右边的子树开始入栈if(p-childrenk!=NULL)stack+top = p-childrenk;marktop = 0;break;/避免重复存入子节点 if(stacktop-children0=NULL|marktop=1)/当节点子树为空或者标记为1时出栈 Visit（data）;层次遍历：void levelorderTree(CTreeNode *ctroot)/树层次遍历非递归if(ctroot=NULL)return;CTreeNode *queueNODENUM,*p;int front=0,rear=0,j;queuerear=ctroot;for(int i=0;iNODENUM;i+)p=queuei;j=0;for(j=0;jchildrenj!=NULL&p!=NULL) queue+rear=p-childrenj;/入队if(i=rear)/节点以全部入队停止循环break; while(frontdata=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=(BTreeNode *)malloc(sizeof(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);/二叉树节点进队列 插入结点：CTreeNode *Insert(CTreeNode *Ctroot,char elem,char parent)/插入元素 CTreeNode *ctchild,*p; int k; fflush(stdin); p=(CTreeNode *)malloc(sizeof(CTreeNode); p-data=elem; for(k=0;kchildrenk=NULL; ctchild=SearchCTree(Ctroot,parent);/查找指定数据的节点 if(ctchild=NULL) return Ctroot;else for(k=0;kchildrenk=NULL) ctchild-childrenk=p; return Ctroot; 删除节点：void Delete(CTreeNode *Ctroot,char elem) CTreeNode *ctchild; int i,j;static int location=0,k=0;if(Ctroot=NULL)return;if(Ctroot-data=elem&location=0)return;location+;for(i=0;ichildreni=NULL)continue; if(Ctroot-childreni-data)=elem) for(j=0;jchildreni)-childrenj)!=NULL)break;if(j=CHILD) Ctroot-childreni=NULL; break; else ctchild=Ctroot-childreni; if(ctchild=NULL) break;/孩子节点遍历结束，退出 elseDelete(ctchild,elem);/递归查找 查找结点：void Search(CTreeNode *Ctroot,char elem)/查找元素 CTreeNode *ctchild; int i;static int flag=0,k=0;static int location=0;if(Ctroot=NULL)return;location+;if(Ctroot-data=elem)return true;if(location=nodenum&flag=0&k=0)return false;for(i=0;ichildreni; if(ctchild=NULL) break;/孩子节点遍历结束，退出 elseSearch(ctchild,elem);/递归查找流程图： 开始输入节点数及结点数据查找父节点N结点找到 子结点放到父节点指针域 Y 结束 图2 创建树 开始N 树存在Y存在孩子结点N Y 结点后移输出结点数据 结束图3 先序递归遍历 开始存入根节点N存在孩子结点 Y 存入第一个孩子 存入节点，指针前移N 已遍历完 Y输出数组元素结束图4 先序非递归遍历开始N 树存在N结点有孩子 Y Y 指向孩子 输出结点数据返回上一个节点N 树遍历完 Y结束图5 后序递归遍历开始 根节点入栈N 存在孩子 Y 输出栈顶结点从指针域由大到小存入栈N 栈为空 Y 栈顶结点出栈 结束图6 后序非递归遍历开始Y 树为空 N 存入根节点N有孩子结点 Y 按顺序存入孩子移向数组中下一个结点输出数组中存入的所有结点 结束图7 树的层次遍历开始输入待查找结点 先序遍历结点N找到数据域相等结点 Y输出找到的位置 结束图8 查找指定结点开始 树为空根结点入树队列，根二叉树队列Y 队为空 N结点出树队列，二叉树队列N 有孩子结点Y 遍历树结点孩子创建对应二叉树结点，数据域存储对应孩子结点数据NY 第一个孩子结点放入前一个出队结点的左孩子放入动态指针指向的当前结点的右孩子动态指针指向当前结点 结束图9 树转化为二叉树开始Y 树为空 N输入插入结点及父结点 遍历树，查找父结点N遍历所有结点找到父结点 Y 将结点插入 结束图10 插入指定结点 开始输入待删除结点遍历树，查找一个结点的孩子结点数据域符合删除条件N存在该结点 YN该结点孩子结点不存在孩子 Y 该结点当前指针域置为空，释放空间 结束图11 删除指定叶子结点四、调试分析 1. 实际完成的情况 本程序完成了树的基本应用内容，包括树的创建，按先序、后序、层次遍历的递归非 递归遍历整棵树，可将树转换成二叉树，并用层次遍历输出转化后的二叉树，可在树中插入、 删除指定结点，可根据需要查找到节点在先序遍历中的位置。建树过程采用字符类型数据建立整棵树。 2、程序的性能分析程序多次采用栈、队列的操作，使数据的读取存储较为快捷。多出进行判断，防止用户的误操作，达到使用的安全性。在树的各遍历过程中时间复杂度均为O（n2），递归过程中空间复杂度为O（1），非递归过程空间复杂度为O（n）（n为节点数）。插入、删除、查找的时间复杂度为O(n),空间复杂度为O（1）。综合考虑了代码的简洁性清楚，模块功能分明，空间的利用率高、运行效率高效、安全性能等多方面的优化，性能较为可观。 3.上机过程中出现的问题及其解决方案上机时主要在树的创建过程中较为麻烦，查阅资料，树的存储形式有多种方法，最后决定采用孩子表示法，以此方便对孩子节点的遍历等操作。之后树与二叉树的转换较为麻烦，参考网上资料，采用队列形式，定义树形队列，二叉树形队列，将节点逐个入队、出队，加之判断操作，达到结点存入二叉树的顺序正确性。删除结点时，由于采用的孩子表示法，无法找到待删除元素时再返回父节点进行删除，此时采用找到父节点，如孩子结点符合删除条件，将父结点对应指针域置为空，释放结点。4. 程序中可以改进的地方说明程序在建树过程中只能采用子结点父结点同时输入，通过查询父结点建树，且输入时子结点与父结点之间不能有空格，使树的建立有了一定的限制。删除结点时不能删除非叶子结点，删除局限性大。5. 程序中可以扩充的功能及设计实现假想 删除带孩子结点时，可以生成多棵树，成为森林，可采用先序遍历输出森林的生成结果。采用数组存储每棵子树，该数组中即为整个森林，然后每棵子树按先序遍历输出即可。还可添加对二叉树转化为树的过程，同树转化为二叉树，采用队列的形式，完成对数转化为二叉树的逆过程，此时即为二叉树转化为树。五、 测试结果1、树的创建： 图12 树的创建2、树的递归先序遍历结果： 图13 树的递归先序遍历结果3、树的非递归先序遍历结果： 图14 树的非递归先序遍历结果4、树的递归后序遍历结果： 图15 树的递归后序遍历结果5、树的非递归后序遍历结果： 图16 树的非递归后序遍历结果6、树的层次遍历结果： 图17 树的层次遍历结果7、树转化为二叉树的层次遍历结果： 图18 树转化为二叉树的层次遍历结果8、插入叶子节点按先序遍历结果显示： 图19 插入叶子节点按先序遍历结果显示9、插入不存在的父结点：图20 插入不存在的父结点10、删除叶子节点： 图21 删除叶子节点11、删除非叶子节点： 图22 删除非叶子节点12、删除节点不存在： 图23 删除节点不存在13、查找指定结点（在树中存在该节点）： 图24 查找指定结点（在树中存在该节点）14、查找指定节点（在树中不存在该节点）： 图25 查找指定节点（在树中不存在该节点）六、 用户手册1、主界面如下，按每个操作的前缀数字进行操作： 图26 主界面2、首先输入1创建一棵树，输入树的结点与父节点之间不要含有空格： 图27 创建一棵树3、输入2进行树的递归先序遍历： 图28 树的递归先序遍历4、输入3进行树的非递归先序遍历： 图29 树的非递归先序遍历5、输入4树的递归后序遍历： 图30 树的递归后序遍历6、输入5树的非递归后序遍历： 图31 树的非递归后序遍历7、输入6树的层次遍历： 图32 树的层次遍历8、输入7树转化为二叉树的层次遍历结果： 图33 树转化为二叉树的层次遍历结果9、输入8插入叶子节点，按2先序遍历结果显示（也可以选择其他遍历显示）： 图34 插入叶子节点10、输入9删除叶子节点（可输入遍历数字进行删除后的显示）： 图35 删除叶子节点11、输入10查找指定结点： 图36 查找指定结点七、体会与自我评价 本次课题是对树的一些常用基本操作，开始对相应的模块功能的思路基本成形，但在相应代码实现过程中才发现有很多细节还需要处理，这也就是影响代码编写进度的关键地方。处理一个编程题关想到思路只是完成一半的任务，动手编写，调试程序，进行细节的处理才是完成整个程序的关键。这就要求在之后的问题处理上要能够着手去做想到的事，这才能完