二叉树的遍历.doc

《二叉树的遍历.doc》由会员分享，可在线阅读，更多相关《二叉树的遍历.doc（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数 据 结 构 课 程 设 计设计题目： 基于文件实现二叉树的三种遍历 学生姓名： 郎金鑫 专业班级： 10计算机科学与技术(1)班 指导教师： 姚丽莎 完成时间： 2012-6-2 信息工程学院院计算机科学院与技术系课题名称基于文件实现二叉树的三种遍历院 系信息工程学院年级专业10计科（1）班学 号姓 名成 绩1042151116郎金鑫课题设计目的与设计意义1、 课题设计目的：一了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；二 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；三 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；四训练用系

2、统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风2、 课题设计意义：锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。指导教师：姚丽莎2012年 06月02日目录1.设计目的42.需求分析52.1课程设计的内容和要求52.2选题背景53.概要设计63.1设计思想63.2函数间的关系84.详细设计84.1二叉树算法源程序84.2程序截图和结果185. 程序测试结果及问题分析196.总结197.参考文献208.附录201.设计目的数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。

3、因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的

4、程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：一、 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；二、 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；三、 提

5、高综合运用所学的理论知识和方法独立分析和解决问题的能力；四训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风2.需求分析2.1课程设计的内容和要求（包括原始数据、技术要求、工作要求等）二叉树的遍历: 对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。画出搜索顺序示意图。2.2选题的意义及背景二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每个结点包含三个域，分别是数据域，左孩子指针域，右孩子指针域。因

6、此每个结点为leftchild data rightchild 由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。可先用这三种遍历输出二叉树的结点。采用递归算法设计，以前序遍历为例，它要求首先要访问根节点，然后前序遍历左子树和前序遍历右子树。特点在于所有未被访问的节点中，最后访问结点的左子树的根结点将最先被访问，这与堆栈的特点相吻合。因此可借助堆栈实现二叉树的递归遍历。将输出结果与递归结果比较来检验正确性，因此程序结果可做成菜单方便这两种算法的结果查看。3.概要设计 3.1设计思想建立一个完全二叉树用堆栈实现的前序遍历：算法思想： (1).初始化一个堆栈 (2).把根

7、节点的指针入栈 (3).当堆栈非空时执行循环步骤a 到步骤 c a. 出栈取得一个结点指针，访问该结点. b. 若该结点的右子树非空，将该结点的右子树指针入栈 c. 若该结点的左子树非空，将该结点的左子树指针入栈 用堆栈实现的中序遍历：算法思想： (1).初始化一个堆栈 (2).将根结点的所有左结点入栈 (3).当堆栈非空时执行循环步骤a 到步骤 d a. 出栈取得一个结点指针 b. 若该结点的右子树非空并且未被访问，将该结点的右子树指针入栈 c. 访问该结点 d. 若该结点的左子树非空并且未被访问，将该结点的左子树指针入栈 用堆栈实现的后序遍历 算法思想： (1).初始化一个堆栈 (2).将

8、根结点的所有左结点入栈 (3)当堆栈非空时执行循环步骤a 到步骤 d a. 出栈取得一个结点指针 b. 若该结点的右子树非空并且未被访问，将该结点的右子树指针入栈 c. 若该结点的左子树非空并且未被访问，将该结点的左子树指针入栈 d. 访问该结点 例如：输入5节点的二叉树。它的前序遍历为：1 2 4 5 3 6 7 它的中序遍历为：4 2 5 1 6 3 7 它的后序遍历为：4 5 2 6 7 3 1 12 3 4 5 6 7 3.2函数关系：图3.1 函数间的关系4.详细设计4.1二叉树算法源程序#include #define STACK_MAXLEN 30/using namespace

9、 std;typedef struct BTreeNodeint where;struct BTreeNode *rightChild;struct BTreeNode *leftChild;TYPE_B_TREE_NODE,*TYPE_pB_TREE_NODE;/堆栈的结构class TStackpublic:void push(TYPE_pB_TREE_NODE pNode);/入栈TYPE_pB_TREE_NODE pop();/出栈int empty()if ( top = base )return 1;elsereturn 0;TStack()top=base=stackArray;

10、for(int i=0; i STACK_MAXLEN; i+)stackArrayi=NULL;/cout堆栈初始化完毕！endl;private:TYPE_pB_TREE_NODE stackArraySTACK_MAXLEN;TYPE_pB_TREE_NODE *top;TYPE_pB_TREE_NODE *base;/指向指针的指针;void TStack:push(TYPE_pB_TREE_NODE pNode)*top=pNode;top+;TYPE_pB_TREE_NODE TStack:pop()TYPE_pB_TREE_NODE returnValue;top-;return

11、Value=(*top);*top=NULL;return returnValue;/建立一个简单的完全二叉树TYPE_pB_TREE_NODE CreateBTree()int i=0;int NodeNum;TYPE_pB_TREE_NODE pBTreeArray,pBTree;cout请输入完全二叉树的节点数：NodeNum;pBTreeArray=new TYPE_B_TREE_NODENodeNum;for(i=1; i = NodeNum/2-1; i+)pBTreeArrayi-1.where=i;pBTreeArrayi-1.leftChild=pBTreeArray+(2*

12、i-1);pBTreeArray2*i-1.where=2*i;pBTreeArrayi-1.rightChild=pBTreeArray+(2*i);pBTreeArray2*i.where=2*i+1;if(2*i+1 = NodeNum )pBTreeArrayi-1.where=i;pBTreeArrayi-1.leftChild=pBTreeArray+(2*i-1);pBTreeArray2*i-1.where=2*i;pBTreeArrayi-1.rightChild=pBTreeArray+(2*i);pBTreeArray2*i.where=2*i+1;elsepBTreeA

13、rrayi-1.where=i;pBTreeArrayi-1.leftChild=pBTreeArray+(2*i-1);pBTreeArray2*i-1.where=2*i;pBTreeArray2*i.rightChild=NULL;for( int j=i+1; j =NodeNum; j+ )pBTreeArrayj-1.leftChild=NULL;pBTreeArrayj-1.rightChild=NULL;return pBTree=pBTreeArray+0;/void PrintBTree(TYPE_pB_TREE_NODE pBTreeRoot)if( pBTreeRoot

14、 != NULL )coutwhereleftChild);PrintBTree(pBTreeRoot-rightChild);/先序遍历void PreOrder(TYPE_pB_TREE_NODE pBTreeRoot)cout先序遍历endl;TStack stack;TYPE_pB_TREE_NODE pTemporary;pTemporary=pBTreeRoot;while( pTemporary != NULL )coutwhereleftChild;while( stack.empty() != 1 )pTemporary=stack.pop();if( pTemporary-

15、rightChild = NULL )continue;elsepTemporary=pTemporary-rightChild;while( pTemporary != NULL )coutwhereleftChild;/中序遍历void InOrder(TYPE_pB_TREE_NODE pBTreeRoot)cout中序遍历endl;TStack stack;TYPE_pB_TREE_NODE pTemporary;pTemporary=pBTreeRoot;while( pTemporary != NULL )/coutwhereleftChild;while( stack.empty

16、() != 1 )pTemporary=stack.pop();coutwhererightChild = NULL )continue;elsepTemporary=pTemporary-rightChild;while( pTemporary != NULL )/stack.push(pTemporary);pTemporary=pTemporary-leftChild;/后序遍历void PostOrder(TYPE_pB_TREE_NODE pBTreeRoot)cout后序遍历endl;TStack stack;TYPE_pB_TREE_NODE pTemporary;int * p

17、Flag;/int withNoChild;int flagSTACK_MAXLEN;for(int i=0; i STACK_MAXLEN ; i+)flagi=0;pFlag=flag;stack.push(pBTreeRoot);while( stack.empty() != 1 )pTemporary=stack.pop();if( *pFlag = 1 )coutwhererightChild !=NULL )stack.push(pTemporary-rightChild);pFlag+;/withNoChild+;if( pTemporary-leftChild !=NULL )

18、stack.push(pTemporary-leftChild);pFlag+;/withNoChild+;void main()TYPE_pB_TREE_NODE pBTreeRoot;pBTreeRoot=CreateBTree();/PrintBTree(pBTreeRoot);PreOrder(pBTreeRoot);InOrder(pBTreeRoot);PostOrder(pBTreeRoot); 4.2 程序结果截图输入节点数为7的二叉树：输入节点为5的二叉树：输入节点为3的二叉树：5. 程序测试结果及问题分析 通过与递归的遍历结果相比较之后，用堆栈实现的非递归遍历算法得出了正确

19、的遍历结果，可以对二叉树进行遍历操作。但是程序中树的结点已经建立好不能随意改动这确实是一个缺点因此可以进行改进，可以用递归的方法建立一棵二叉树，先建立左子树，在建立右子树这样用户输入的字符可以直接用来建树程序的灵活性会更强。6.总结通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并二叉树的算法有了更加深刻的了解，更巩固了课堂中学习有关于二叉树的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。这次课程设计，我在编辑中犯了不应有

20、的错误，设计统计字符和合并时忘记应该怎样保存保存数据，在不断分析后明确并改正了错误和疏漏，使我的程序有了更高的质量。这不仅是程序设计,更是锻炼我们处理问题的能力,同时也使我们了解到团队合作的可贵.编写程序是件细心活,稍不留神就会出错,这就必须要求我们对待事情要认真!在编写程序的过程中,错误不断出现,不同的类型(如少写了一个符号,写错了字母,用错了函数等等)层出不穷,这考验我们待事细心,耐心,能不能坚持到底,不能半途而废。三人行必有我师,遇到问题我们一起讨论,研究,错了再写,写了在改.经过多次的修改,调试,运行,添加,终于最后在大家的欢呼声中,完成了我们的任务.虽说是累了点，但我们也从中找到了自己的快乐，每当完成一个新的函数时，那心情是激动啊,这毕竟是自己弄出来的,同时也使我感受到了学习的快乐！7.参考文献1严蔚敏，吴伟民数据结构：C语言版M清华大学出版社19922陈维兴，林小茶.C+面向对象程序设计教程（第三版）M清华大学出版社19913徐德民.最新C语言程序设计M电子工业出版社1992年4唐策善，黄刘生.数据结构M中国科学技术出版社.1992年5仲萃豪，冯玉琳.程序设计方法学M北京科学技术出版社1985年8.附录：源程序见附件 源程序.doc20