数据结构课程设计报告封面.doc

数据结构课程设计报告题目: 二叉树的遍历的实现  院(系):计算机工程学院专  业:嵌入式系统开发与设计班  级: 嵌入式109(1) 学  生:   邓 涛    指导教师:  寇海洲 孙成富  邱军林 殷 路  2010年12月目录一、设计要求  1二、设计题目  1三、程序设计步骤  2四、调试与分析  8五、测试修改  9六、课程设计小结  12一、设计要求1、根据实际情况以及数据结构的课程,结合一些算法思想和个人创新来编写实现一些实际问题。2、提高个人编写代码的能力,包括编写算法,调试程序,测试程序,修改算法,改良算法等能力。3、认识软件开发的流程,初步掌握软件开发的方法和思想。4、规范代码的编写方法和编写格式,培养良好的编写代码作风,规范代码格式。5、培养借鉴参考文献的能力。二、设计题目1、系统名称:二叉树遍历的实现2、要求:(1)建立二叉树,可用各种方法建树,一般建议使用满二叉树的层次序号的排列顺序。(2)使用多种方法遍历全树。①递归算法实现先序,中序,后序遍历;②非递归算法实现先序,中序,后序的遍历。层次遍历的实现(非递归短发实现)三、程序设计步骤1)功能分析说明图:2)采用主要的数据结构类型。1建树过程使用队列的存储结构,队列特点满足先进先出。建立链表由用户输入值,将输入的值按照满二叉树的顺序存储,通过队列(以数组为存储方式)来分配内存空间接下来使front当前数组移动,使用户下一个值分配到其左右节点,区别左右节点的方法是而叉树的性质,当为奇数个它是右孩子,*Creat_DTtree(){into=1;DTtree*Q[max];DataTypech;intfront,rear;DTtree*s,*root;root=NULL;front=1;rear=0;printf("*****************请按照完全二叉树的编号顺序依次输入结点序列*********************");printf("\t\t<注:空结点用'@'表示,输入序列以'#'结束>\n");ch=getchar();while(ch!='#'){s=NULL;if(ch!='#'){s=(DTtree*)malloc(sizeof(DTtree));         /*建立二叉树的第一个根节点,根节点为输入的第一个ch的直,左右孩子为空*/s->data=ch;s->lchild=NULL;s->rchild=NULL;}rear++;                       /*队列第一个从数组下表为1的存储单元开始存储*/              if(o==1)                      /*层次遍历的顺序即为存入二叉树的顺序*/{printf("层次遍历结果为:");}     Q[rear]=s;                      /*数组指针指向s的根节点*/printf("%c",Q[rear]->data);if(rear==1)                     /*确定返回值:root*/root=s;else{if(s&&Q[front])                 /*满足指针s和当前的数组指针都不为空*/if(rear%2==0)                  /*当为第偶数个结点时,将s给指针的左孩子,奇数为右孩子*/Q[front]->lchild=s;elseQ[front]->rchild=s;             if(rear%2==1)front++;}ch=getchar();o--;if(ch!='#'){printf("->");}}a=rear,b=rear,c=rear,d=rear,e=rear,f=rear,g=rear;returnroot;}2先序的遍历顺序是:根节点-〉左子树-〉右子树;因此先序递归算法较为简单,只是一个方法的递归调用。在访问当前根节点之后,在方法中再次调用该方法,遍历当前根节点的左子树和右子树即可。非递归的算法较为复杂,要使用到栈的概念。现访问这个根节点并将其右节点进栈,使指针指向其左孩子,再次进行上述循环,直到其没有做孩子时,使右孩子出栈,当前的右孩子在进行上述的循环。直到完成遍历/*先序的非递归算法*/voidpreorder_1(DTtree*t)     {inttop=0;DTtree*p,*s[max];       p=t;do{while(p!=NULL){printf("%c",p->data);if(e>1)printf("->");if(p->rchild!=NULL)s[top++]=p->rchild;  p=p->lchild; e--;