《数据结构》课程设计论文- 二叉树的遍历.doc

数据结构课程设计题 目 二叉树的遍历学 号：_ _姓 名：_ _指导教师：_ _成 绩：_完成时间：_2011 年 _12 月目录1、需求分析12、概要设计22.1 功能设计22.2 算法流程图33、详细设计43.1 界面设计43.2 详细代码分析53.3 调试分析113.3.1调试结果143.3.2算法分析144、总结14参考文献15151、需求分析数据结构是计算机、信息管理、信息与计算机科学等信息类专业最重要的专业基础课程，掌握好数据结构的知识将直接关系到后续专业课程的学习。数据结构只要研究四个方面的问题：(1)数据的逻辑结构，即数据之间的逻辑关系；(2)数据的物理结构，即数据在计算机内的存储方式；(3)对数据的加工，即基于某种存储方式的操作算法；(4)算法的分析；即评价算法的优劣。本实验是用链式存储结构来存储二叉树并进行一系列的算法，且结点内容的数据类型为字符型。本程序用VC+6.0编写，可以实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归算法，先序遍历、中序遍历、后序遍历的非递归算法以及 能查找任一结点在某种遍历序列中的前驱和后继。根据题目知，程序主要是根据给定二叉树的先序遍历结果，构造出二叉树并输出按中，后序遍历的结果，以及求二叉树的叶子个数等。其中二叉树的结点用字符表示。(1) 先创建二叉树：构建一个字符二叉树实例，并横向打印该二叉树。(2)设计算法:用递归算法和非递归算法中序遍历和后序遍历这个二叉树。 (3)加入求二叉树的深度和二叉树的叶子数二叉树的结点总数等一些简单的算法 。(4) 设计main()函数调用以上步骤实现相关功能。2、概要设计2.1 功能设计（1）CreateBSTNode(char *s)此函数的功能是构建一个二叉树。（2）DispBTree(BSTNode *b)此函数的功能是打印该二叉树。（3）BSTNodeDepth(*b) 此函数的功能是求该二叉树高度。（4）DispLeaf(BSTNode *b) 此函数的功能是在屏幕上输出该二叉树的叶子结点。（5）InOrder(BSTNode *b) 此函数的功能是用递归的方法实现二叉树的中序遍历算法。 PostOrder(BSTNode *b) 此函数的功能是用递归的方法实现二叉树的后序遍历算法。（6）InOrder2(BSTNode *b) 此函数的功能是用非递归的方法实现二叉树的中序遍历算法。 PostOrder2(BSTNode *b) 此函数的功能是用非递归的方法实现二叉树的后序遍历算法。2.2 算法流程图 先设计出二叉树的一些算法的函数，如非递归的中序和后序遍历、递归的中序和后序遍历、求二叉树的高度和输出其叶子结点等一些算法。然后在主函数中逐一调用。 算法流程图如图1所示。Main()CreateBSTNode()构造二叉树InOrder()PostOrder()分别输出递归的中、后序遍历结果InOrder2()PostOrder2()分别输出非递归的中、后序遍历结果DispBTree(）打印该二叉树输出二叉树的叶子结点高度BSTNodeDepth()DispLeaf（） 图 1 算法流程图3、详细设计3.1 详细代码设计（1）构造二叉数 若ch=(：则将前面刚创建的结点作为双亲结点进栈,并置k=1,表示其后创建的结点将作为这个结点的左孩子结点； 若ch=)：表示栈中结点的左右孩子结点处理完毕,退栈； 若ch=,：表示其后创建的结点为右孩子结点；BSTNode* CreateBSTNode(char *s) char ch;BSTNode *p=NULL,*b=NULL,*psMaxSize; int top=-1,tag=-1;ch=*s; while(ch) switch(ch) case (:ps+top=p;tag=1;break; case ,:tag=2;break; case ):top-;break; default: p=(BSTNode*)malloc(sizeof(BSTNode); p-data=ch; p-lchild=p-rchild=NULL; if(b=NULL) b=p; elseswitch(tag) case 1:pstop-lchild=p;break; case 2:pstop-rchild=p;break; ch=*(+s); return b; (2) 打印二叉树DispBTree(BSTNode *b)根据每个结点的层次和高度把他们用DispBTree打印出来。 void DispBTree(BSTNode *b) int n,i,j,high,level; PBSTNode *p; PBSTNode *pquMaxSize; PBSTNode *levelpquMaxSize; n=CreatePBSTNode(b,pqu); high=BSTNodeHeight(b);j=0;level=1; pqu0-space=Pstart; for(i=0;ilevel=level) levelpquj=p; j+; else PBSTNodePrint_char(levelpqu,j,high);level=p-level; j=0;levelpquj=p;j+; PBSTNodePrint_char(levelpqu,j,high);（4）非递归的中序遍历算法此函数的功能是用非递归的方法实现二叉树的中序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。void InOrder2(BSTNode *b) BSTNode *StMaxSize,*p; int top=-1; p=b; while (top-1 | p!=NULL) while (p!=NULL) /扫描*p的所有左结点并进栈 top+; Sttop=p; p=p-lchild; if (top-1) p=Sttop;top-; /出栈*p结点 printf(%c ,p-data); /访问之 p=p-rchild; /扫描*p的右孩子结点 /end of while(top-1 | p!=NULL) （5）非递归的后序遍历算法 如何判断一个结点*b的右孩子结点已访问过，为此用p保存刚刚访问过的结点（初值为NULL），若b-rchild=p成立（在后序遍历中，*b的右孩子结点一定刚好在*b之前访问），说明*b的左右子树均已访问，现在应访问*b。 void PostOrder2(BSTNode *b) BSTNode *StMaxSize;BSTNode *p; int flag,top=-1;/栈指针置初值 do while (b!=NULL) /将*b的所有左结点进栈 top+; Sttop=b; b=b-lchild; p=NULL; /p指向栈顶结点的前一个已访问的结点 flag=1; /设置b的访问标记为已访问过 while (top!=-1 & flag=1) b=Sttop; /取出当前的栈顶元素 if (b-rchild=p) printf(%c ,b-data);/访问*b结点 top-;p=b;/p指向则被访问的结点 else b=b-rchild;/b指向右孩子结点 flag=0;/设置未被访问的标记 /end of while (top!=-1 & flag=1) while (top!=-1); （6）递归的中序遍历函数功能是用递归的方法对二叉树进行中序遍历。算法思想：若二叉树为空，则结束遍历操作；否则中序遍历根的左子树；访问根结点；中序遍历根的右子树。void InOrder(BSTNode *b) /*中序遍历的递归算法*/ if (b!=NULL) InOrder(b-lchild); printf(%c ,b-data); /*访问根结点*/ InOrder(b-rchild); （7）递归的后序遍历函数功能是用递归的方法对二叉树进行中序遍历。算法思想：若二叉树为空，则结束遍历操作；否则后序遍历根的左子树；后序遍历根的右子树；访问根结点。void PostOrder(BSTNode *b) /*后序遍历递归算法*/ if (b!=NULL) PostOrder(b-lchild); PostOrder(b-rchild); printf(%c ,b-data); /*访问根结点*/ (8) 输出叶子结点DispLeaf(BSTNode *b) 输出一棵二叉树的所有叶子结点的递归模型f()如下： f(b)：不做任何事件 若b=NULL f(b)：输出*b结点的data域 若*b为叶子结点 f(b)：f(b-lchild);f(b-rchild) 其他情况 void DispLeaf(BSTNode *b) if (b!=NULL) if (b-lchild=NULL & b-rchild=NULL) printf(%c ,b-data); else DispLeaf(b-lchild); DispLeaf(b-rchild); (9) 求高度BSTNodeDepth(*b) 求二叉树的高度的递归模型f()如下： f(NULL)=0 f(b)=MAXf(b-lchild),f(b-rchild)+1 其他情况 对应的算法如下： int BSTNodeDepth(BTNode *b) int lchilddep,rchilddep; if (b=NULL) return(0); /*空树的高度为0*/ else lchilddep=BSTNodeDepth(b-lchild); /*求左子树的高度为lchilddep*/ rchilddep=BTNodeDepth(b-rchild); /*求右子树的高度为rchilddep*/ return(lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); (10)主函数的程序void main() int iDepth=0,iWidth=0,iCount=0;char *str1=A(B(D,E(H,X(J,K(L,M(T,Y),C(F,G(X,I);char *str2=A(B(D(,G),C(E,F);BSTNode *b=CreateBSTNode(str1);DispBSTNode(b);printf(n);iDepth=BSTNodeHeight(b);printf(Depth:%dn,iDepth);DispBTree(b);printf(leaf:%c ,b-data); DispLeaf(b);printf(n); printf(递归中序遍历:%c ,b-data); InOrder(b); printf(n); printf(递归后序遍历:%c ,b-data); PostOrder(b);printf(n); printf(非递归中序遍历:%c ,b-data); InOrder2(b);printf(n); printf(非递归后序遍历:%c ,b-data); PostOrder2(b);printf(n);3.3 调试分析(1) 创建二叉树图2所示：图 2创建二叉树（2）求二叉树的叶子结点，求出的结点如图3所示：图 3求二叉树的叶子结点（3）求二叉树的深度，创建后的二叉树的深度如图4所示：图 4求二叉树的深度（4）二叉树的递归遍历算法（中、后）递归的中序遍历如图5所示：图 5递归的中序遍历 递归的后序遍历如图6所示：图 6递归的后序遍历（3）二叉树的非递归遍历算法（中、后）,非递归的中序遍历如图7所示：图 7非递归的中序遍历非递归的后序遍历如图8所示：图 8非递归的后序遍历3.3.2算法分析本程序按递归遍历所耗费的时间复杂度为O（n），其所耗费的空间复杂度也为O（n）。4、总结 虽然都说“程序数据结构算法”，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。我感受最深的一点是：以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。我以前对递归算法一直很害怕，总是看不明白究竟这递归是怎么进行的。在这次实验中我终于克服了这一障碍，一次次单步执行书中递归函数的例子，并一遍遍在心中自己默默的走，终于弄明白了，真的是功夫不负有心人啊！同时我还根据自己的理解写出了类似的递归函数实现了新的功能，真是受益良多啊！在这次实验中，我对参数的调用也进行了很多种尝试，已差不多经能够选择合适的参数形式来实现函数之间的数据传