资源描述：
《数据结构——二叉树的遍历》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、信息科学与技术学院《数据结构》课程设计报告题目名称：二叉树的遍历专业班级：11111111111学生学号：11111指导教师：11111完成日期:2013-01-091课程设计的目的31.1课程设计的冃的32概要设计32.1总体组成框图32.2基本操作43详细设计43.1流程图43.2源程序64测试214.1创建二叉树214.2二叉树的递归遍历（以先序为例）214.3二叉树的非递归遍历（以先序为例）224.4层次序遍历:224.5二叉树与树的转换:235课程设计总结246参考书目:251课程设计的目的1.1课程设计的H的培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的
2、动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生叮以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。1.2课程设计的题冃二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。1.3题目要求遍历的内容应是T姿百态的。树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。2概要设计2.1总体组成框图2.2基木操作〃队列数据类型定义typedefstruct{BiTreeNod
3、equeue[maxsize];intrear;//队尾指针intfront;//队头指针intcount;//计数器}SeqCQueue;//栈数据类型定义typedefstruct//堆栈的结构体，用于非递归的后序遍历{stacknodeElem[maxsize];inttop;}SequenceStack;主要模块设计voidPreOrder(BiTreeNode*root,voidVisit(charitem))；//先序递归遍历二叉树voidTnOrder(BiTreeNode*root,voidVisit(charitem))://中序递归遍历二叉树voidPostOrd
4、er(BiTreeNode*root,voidVisit(charitem))；//后序递归遍历二叉树voidPreOrderUnrec(BiTreeNode*t)；//先序非递归遍历一叉树voidInOrderUnrec(BiTreeNode*t)；//屮序非递归遍历二叉树voidPostOrderUnrec(BiTreeNode*t)；//后序非递归遍历二叉树voidccbl(BiTreeNode*h)：//层次遍历英他模块包括栈的初始化及英基本操作和队列的初始化及基本操作。3详细设计3.1流程图二叉树的递归遍历（以先序遍历为例）结束二叉树的非递归遍历（以先序遍历为例）二叉树的层
5、次遍历访问元素所指结点，若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。3.2源程序#include#includeusingnamespacestd;#definemaxsize100structnode{inti;node*next;};structtreenode{inti;treenode}；nodenod[105],temp[1005];intedge,tt,qq[1000],head,tail;treenodetn[105];voidchangel(intk){if(nod[k].next==NUL
6、L)return;inti,j；node*p;for(p=nod[k],nextJ=0;p!=NULL;p=p->next){i=p->i；if(j==O){tn[k].l=&tn[i];changel(i);j=l；}else{tn[i].r=tn[k].l->r;tn[k].l->i-&tn[i];changel(i);voidbfsl(intsum)if(sum==O)return;inti,j,k=O;for(i=1;iv二sum;i++){j=qqfhead++l;if(tn[j].l!=NULL){cout«j«tn
7、j].l->i«endl;qq[tail++]=tn
8、
9、jj.l->i;k++;}if(tn[j].r!=NULL){cout«j«tnlj].l->i«endl;qq[tail++]=tn[j].r->i;k++;}}bfsl(k);}voidfun1()〃树转换二叉树{memset(nod,0,sizeof(nod));cout«H输入树，结点1默认位根结点M«endl;cout«n输入边数：M«endl;cin»edge;inti,j,k=O,x,y；coutvv“以父亲指向儿了方式输入边信Mn«en
