数据结构课程设计-二叉树的遍历算法集成.doc

安徽理工大学数据结构课程设计说明书题目: 二叉树的遍历算法集成 院 系： 计算机科学与工程学院专业班级： 学 号： 学生姓名： 指导教师： 2010年1月11日安徽理工大学课程设计（论文）任务书 计算机科学与工程 学院 计算机软件教研室学 号2008303003学生姓名刘威专业（班级）信息08-1设计题目 二叉树的遍历算法集成设计技术参数系统平台：Windows XP开发工具： VC+ 6.0设计要求（1）界面友好，易于操作。可采用菜单或其它人机对话方式进行选择（2）实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归或非递归算法。（3）要求能查找任一结点在某种遍历序列中的前驱和后继。（4）演示程序以人机对话的形式进行。每次测试完毕正确显示各种遍历序列。工作量课程设计报告要求不少于3000字。源程序要求不少于300行工作计划12月14日- 12月16日 查找相关资料12月18日- 12月21日 思考相关问题12月22日-12月28日 设计算法12月29日-1月05日 编写代码1月06日-1月09日 撰写课程设计报告参考资料1 秦锋. 数据结构(C语言版).合肥:中国科学技术大学出版社,2007 2 温秀梅.Visual C+面象对象程序设计教程与实验.北京：清华大学出版社20063 何钦铭.C语言程序设计.北京:高等教育出版社，2008指导教师签字教研室主任签字 2009年 11 月 16 日 学生姓名： 刘威 学号：2008303003 专业班级： 信息08-1 课程设计题目： 二叉树的遍历算法集成 指导教师评语： 成绩： 指导教师： 年 月 日安徽理工大学课程设计（论文）成绩评定表目录1、需求分析12、概要设计22.1 功能设计22.2 算法流程图33、详细设计43.1 界面设计43.2 详细代码分析53.3 调试分析143.3.1调试结果143.3.2算法分析184、总结18参考文献19191、需求分析数据结构是计算机、信息管理、信息与计算机科学等信息类专业最重要的专业基础课程，掌握好数据结构的知识将直接关系到后续专业课程的学习。数据结构只要研究四个方面的问题：(1)数据的逻辑结构，即数据之间的逻辑关系；(2)数据的物理结构，即数据在计算机内的存储方式；(3)对数据的加工，即基于某种存储方式的操作算法；(4)算法的分析；即评价算法的优劣。本实验是用链式存储结构来存储二叉树并进行一系列的算法，且结点内容的数据类型为字符型。本程序用VC+6.0编写，可以实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归算法，先序遍历、中序遍历、后序遍历的非递归算法以及 能查找任一结点在某种遍历序列中的前驱和后继。根据题目知，程序主要是根据给定二叉树的先序遍历结果，构造出二叉树并输出按中，后序遍历的结果，以及求二叉树的叶子个数等。其中二叉树的结点用字符表示。(1) 先创建二叉树：按先序次序输入，构造二叉链表表示的二叉树。(2)设计算法：先序遍历,中序遍历,后序遍历. 在做到层序遍历时，应注意算法如下：根结点入队，队头元素出队，左孩子不为空入队右孩子不为空入队的顺序进行。(3)可以加入求二叉树的深度二叉树的叶子数二叉树的结点总数等一些简单的算法 。(4) 设计main()函数调用以上步骤实现相关功能。2、概要设计2.1 功能设计（1）typedef struct BTNode定义一个用链式存储结构存储的二叉树，其中包括左孩子和右孩子以及数据元素的内容。和单链表类似，一个二叉链表由头指针唯一确定，若二叉树为空，则头指针指向空。并且结点内容的数据类型为字符型。（2）CreateBiTree(BiTree &T) 此函数的功能是构建二叉树。从键盘上按先序次序输入字符构造二叉链表表示的二叉树T，其中用星号表示空树 。（3）NRPreOrder(BiTree bt) 此函数的功能是用非递归的方法实现二叉树的先序遍历算法。调用此函数可以获得二叉树的非递归的先序遍历的结果。（4）NRInOrder(BiTree bt)此函数的功能是用非递归的方法实现二叉树的中序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。（5）NRPostOrder(BiTree bt)此函数的功能是用非递归的方法实现二叉树的后序遍历算法。调用此函数可以获得二叉树的非递归的后序遍历的结果。其中bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志tag一同入栈1：遍历左子树的现场保护，2：遍历右子树前的现场保护。首先将bt和tag(为1)入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。（6）PreOrderTraverse(BiTree T) 函数功能是用递归的方法对二叉树进行先序遍历，调用此函数可以获得二叉树的递归的先序遍历的结果。（7）InOrderTraverse(BiTree T)函数功能是用递归的方法对二叉树进行中序遍历，调用此函数可以获得二叉树的递归的中序遍历的结果。（8）PostOrderTraverse(BiTree T)函数功能是用递归的方法对二叉树进行后序遍历，调用此函数可以获得二叉树的递归的后序遍历的结果。（9）LevelOrderTraverse(BiTree T)调用此函数可以获得二叉树的层序遍历。（10）BTDepth(BiTree T)求二叉树的深度的算法。（11）Leaf(BiTree T)求二叉树的叶子数的算法。（12）NodeCount(BiTree T)求二叉树的结点总数的算法。（13）main()主函数用while()与switch(select)语句对二叉树的操作的算法进行了设计。可以实现以上函数的功能，并能退出程序。2.2 算法流程图 先设计出二叉树的一些算法的函数，如非递归遍历、递归遍历、层次遍历等一些算法。然后在主函数中逐一调用。其中，在求任意结点在中序遍历前驱后继算法时利用了递归的中序遍历的算法。 算法流程图如图1所示。Main()CreateBiTree ()构造二叉树PreOrderTraverse()NRPreOrder（）分别输出递归与非递归先序遍历结果InOrderTrave（）NRInOrder（）分别输出中序递归与非递归遍历结果PostOrderTravesr()NRPostOrder（）分别输出递归与非递归的后序遍历结果求结点的中序前驱后继中序InOrderTraver（） 图 1 算法流程图3、详细设计3.1 界面设计设计的界面如图2所示。图2 界面3.2 详细代码设计（1）定义二叉树用链式存储结构存储二叉树。其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。定义二叉树结点值的类型为字符型且结点个数不超过10个。typedef char ElemType;/结点个数不超过10个const int MaxLength=10;typedef struct BTNodeElemType data;struct BTNode *lchild,*rchild;BTNode,* BiTree;（2）查找模块（2）构造二叉链表创建二叉链表存储的二叉树。按二叉树带空指针的先序次序输入结点值，结点类型为字符型。按先序次序输入，其中*表示空结点。算法是按照先序遍历思想设计的。构造二叉链表表示的二叉树T，星号表示空树。void CreateBiTree(BiTree &T)char ch;ch=getchar();if(ch=*) T=NULL;elseif(!(T=(BTNode *)malloc(sizeof(BTNode) coutdata=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);（3）非递归的先序遍历算法函数功能是用非递归的方法对二叉树进行先序遍历。通过分析可知最后处理过的结点的右子树应该首先被访问，最先处理过的结点的右子树应该最后被访问，显然使用栈可以解决问题。void NRPreOrder(BiTree bt)BiTree stackMaxLength,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top0)while(p!=NULL)coutdatalchild;if (top0) top-;p=stacktop;p=p-rchild;（4）非递归的中序遍历算法此函数的功能是用非递归的方法实现二叉树的中序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。用非递归调用也得使用栈。void NRInOrder(BiTree bt)BiTree stackMaxLength,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top0)while(p!=NULL) stacktop=p; top+; p=p-lchild;if (top0) top-;p=stacktop;coutdatarchild;（5）非递归的后序遍历算法此函数的功能是用非递归的方法实现二叉树的后序遍历算法。调用此函数可以获得二叉树的非递归的后序遍历的结果。其中bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志tag一同入栈1：遍历左子树的现场保护，2：遍历右子树前的现场保护。首先将bt和tag(为1)入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。typedef struct BiTree ptr; int tag;stacknode;void NRPostOrder(BiTree bt) stacknode sMaxLength,x; BiTree p=bt;int top;if(bt!=NULL) top=0;p=bt; do while (p!=NULL) stop.ptr = p; stop.tag = 1; top+; p=p-lchild; while (top0 & stop-1.tag=2) x = s-top; p = x.ptr; coutdata0) stop-1.tag =2; p=stop-1.ptr-rchild; while (top0);（6）递归的先序遍历函数功能是用递归的方法对二叉树进行先序遍历，调用此函数可以获得二叉树的递归的先序遍历的结果。算法思想：若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历根的左子树；先序遍历根的右子树。void PreOrderTraverse(BiTree T)if(T)coutdatalchild);PreOrderTraverse(T-rchild);（7）递归的中序遍历函数功能是用递归的方法对二叉树进行中序遍历。算法思想：若二叉树为空，则结束遍历操作；否则中序遍历根的左子树；访问根结点；中序遍历根的右子树。void InOrderTraverse(BiTree T)if(T)InOrderTraverse(T-lchild);coutdatadata;i+;InOrderTraverse(T-rchild);（8）递归的后序遍历函数功能是用递归的方法对二叉树进行中序遍历。算法思想：若二叉树为空，则结束遍历操作；否则后序遍历根的左子树；后序遍历根的右子树；访问根结点。void PostOrderTraverse(BiTree T)if(T)PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);coutdata ;（9）层序遍历调用此函数可以获得二叉树的层序遍历。该算法的思想如下：访问根结点，并将该结点记录下来；若记录的所有节点都已经处理完毕，则结束遍历操作；否则重复下列操作。取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问做孩子，并记录下来；若它有右孩子，则访问右孩子，并记录下来。void LevelOrderTraverse(BiTree T)BiTree QMaxLength;int front=0,rear=0;BiTree p;/根结点入队if(T) Qrear=T;rear=(rear+1)%MaxLength; while(front!=rear)/队头元素出队p=Qfront; front=(front+1)%MaxLength; coutdatalchild) Qrear=p-lchild;rear=(rear+1)%MaxLength;/右孩子不为空，入队if(p-rchild) Qrear=p-rchild;rear=(rear+1)%MaxLength;（10）结点在中序遍历的前驱后继 此程序所用的方法并非利用线索二叉树。对整个二叉树进行中序遍历，看看哪个结点之后是所求结点的前驱，则该结点就是所求结点的中序前驱。同样的也可以得到中序后继。int i;char a100;void InOrderTraverse(BiTree T)if(T)InOrderTraverse(T-lchild);coutdatadata;i+;InOrderTraverse(T-rchild);上面是利用的二叉树的中序遍历方法来获得结点的信息，再调用下面语句便可实现以上功能。在主函数中应用switch()语句。coutc; for(j=0;ji;j+)if(aj=c)cout结点的前驱为:naj-1endl结点的后继为:naj+1; break;3.3 调试分析3.3.1调试结果(1)系统界面 系统主界面如图3所示。图 3 主界面(2) 创建二叉树 创建后的二叉树如图4所示。图 4创建二叉树（3）二叉树的非递归遍历算法（前、中、后）非递归遍历如图5所示。图 5二叉树的非递归遍历算法（前、中、后）（4）二叉树的递归遍历算法（前、中、后） 递归遍历如图6所示。图 6二叉树的递归遍历算法（前、中、后）（5）二叉树的层次遍历算法 层次遍历如图7所示。图 7 二叉树的层次遍历算法（6）求二叉树的深度 创建后的二叉树的深度如图8所示。图 8求二叉树的深度（7）求二叉树的叶子结点 求出的结点的个数如图9所示。图 3求二叉树的叶子结点（8）求二叉树的结点总数 求出的结点总数如图10所示。图 10求二叉树的结点总数（9）求结点在中序遍历的前驱后继 任意一结点的前驱后继如图11所示。图 11求结点在中序遍历的前驱后继3.3.2算法分析本程序按递归遍历所耗费的时间复杂度为O（n），其所耗费的空间复杂度也为O（n）。4、总结 虽然都说“程序数据结构算法”，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。我感受最深的一点是：以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需