数据结构二叉树的算法课程设计报告.doc

计算机工程学院课程设计报告课程名称：数据结构课程设计设计题目： 二叉树的算法 院 系： 计算机工程学院 专 业： 计算机科学与技术 组 别： 47 学生姓名: 姚燕 学 号: 1101301231 起止日期: 2011年12月19日2011年12月26日指导教师: 张亚红 孙成富 邱军林 窦海洲 目录1需求分析11.1课程设计题目、任务及要求11.2课程设计思想11.3软硬件运行环境及开发工具12概要设计22.1各功能模块流程图22.2 创建二叉树22.3二叉树的递归遍历算法（先、中、后）22.3.1先序遍历22.3.2中序遍历22.3.3后序遍历22.4二叉树的非递归遍历算法（前、中、后）32.4.1非递归的先序遍历算法32.4.2非递归的中序遍历算法32.4.3非递归的后序遍历算法32.5层次序遍历32.6退出33详细设计和实现33.1主要功能模块设计33.2主程序设计44调试与操作说明64.1程序调试64.2程序操作说明6总 结9致谢10参考文献101需求分析1.1课程设计题目、任务及要求二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。要求：遍历的内容应是多样的。1.2课程设计思想首先按先序次序建立一个二叉树，递归遍历，包括先序、中序、后序递归遍历。三种不同次序的遍历二叉树的递归算法的结构相似，只是访问结点及遍历左子树、遍历右子树的先后次序不同而已。在递归执行过程中，先序遍历是每进入一层递归调用时先访问根结点，再依次向它的左、右子树递归调用。中序遍历是在从左子树递归调用退出时访问根结点，然后向它的右子树递归调用。后序遍历是在从左、右子树递归调用后，再访问根结点。把一个递归过程改为非递归过程一般需要利用栈，记录遍历时的回退路径。利用栈的先序遍历二叉树（非递归）：每次访问一个结点后，在向左子树遍历下去之前，利用这个栈记录该结点的右子女（如果有的话）结点的地址，以便在左子树退回时可以直接从栈顶取得右子树的根结点，继续右子树的先序遍历。利用栈的中序遍历二叉树（非递归）：首先访问的是中序下的一个结点，它位于从根开始沿左子树链走到最左下角的结点，该结点的左子树指针为空。访问它的数据之后，再遍历该结点的右子树。此右子树又是二叉树，重复执行上面的过程，直到该子树遍历完。结束条件为：栈为空的同时遍历指针也为空。利用栈的后序遍历二叉树（非递归）：在遍历完左子树是还不能访问根结点，需要再遍历右子树。右子树遍历完后才访问根结点。所以在栈记录中必须注明刚才是在左子树还是右子树中。，在算法中首先使用栈暂存根结点地址，再向左子树遍历下去，此时根结点的tag=1。访问完左子树结点并退回时，还要遍历根的右子树，此时改根结点的tag=2.在从右子树中退出时才访问位于栈顶的根结点的值。层次序遍历从二叉树的根结点开始，自上而下，自左向右分层依次访问树中的各个结点。访问二叉树的处理需要利用一个队列。在访问二叉树的某一层结点是，把下一层结点指针预先记忆在队列中，利用队列安排逐层访问的次序。每访问一个结点时，将它的子女依次加到队列的队尾，然后再访问已在队列队头的结点。这样可以实现二叉树结点的按层访问。1.3软硬件运行环境及开发工具Windows2000以上操作系统、Microsoft Visual C+ 6.02概要设计Main（）CreateBiTree构造二叉树二叉树的递归遍历层次遍历二叉树的非递归遍历退出2.1各功能模块流程图图2.1.2主函数流程图(b)2.2 创建二叉树(1)定义二叉树结点值的类型为字符型。(2)结点个数不超过20个。(3)按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树。2.3二叉树的递归遍历算法（先、中、后）2.3.1先序遍历(1)访问根结点。(2)先序遍历根结点的左子数。(3)先序遍历根结点的右子数。2.3.2中序遍历(1)先序遍历根结点的左子数。(2)访问根结点。(3)先序遍历根结点的右子数。2.3.3后序遍历(1)先序遍历根结点的左子数。(2)先序遍历根结点的右子数。(3)访问根结点。2.4二叉树的非递归遍历算法（前、中、后）2.4.1非递归的先序遍历算法(1)访问结点的数据域。(2)指针指向p的左孩子结点。(3)从栈中弹出栈顶元素。 (4)指针指向p的右孩子结点。2.4.2非递归的中序遍历算法(1)指针指向p的左孩子结点。(2)从栈中弹出栈顶元素。(3)访问结点的数据域。(4)指针指向p的右孩子结点。2.4.3非递归的后序遍历算法bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志一同入栈。首先将bt和标记(为1)入栈，遍历左子树；返回后，修改栈顶标记为2，遍历右子树；最后访问根结点。2.5层次序遍历(1)访问该元素所指结点。(2)若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。2.6退出3详细设计和实现3.1主要功能模块设计程序主要设计了五个功能：首先是创建二叉树, 按先序次序输入，构造二叉链表表示的二叉树T，#表示空树。其余还有四个模块，包括：二叉树的递归遍历算法（先序、中序、后序）；层次序遍历；二叉树的非递归遍历算法（先序、中序、后序）；退出。主函数流程如下：开始Switch(0)输开始入一个数退出Switch(1)建立二叉树Switch(2)二叉树的递归遍历算法（先、中、后）Switch(3)层次遍历Switch(4)二叉树的非递归遍历算法（先、中、后）default提示出错是是是是是是否否否 否否是是是是是是图3.1.1主函数流程图（a）3.2主程序设计void main()BiTree T;T=NULL;int select;/cout请按先序次序输入各结点的值，以#表示空树(输入时可连续输入):endl;/ CreateBiTree(T);while(1)coutn请输入要执行的操作的序号:n; cout1.创建二叉树n; cout2.二叉树的递归遍历算法（前、中、后）n; cout3.二叉树的非递归遍历算法（前、中、后）n;cout4.二叉树的层次遍历算法; coutselect;switch(select)case 0:return;case 1: cout先序次序输入二叉树，以#表示空树(输入时可连续输入):endl; CreateBiTree(T); break; case 2: if(!T) cout未建立树; else coutn先序遍历:n; PreOrderTraverse(T); coutn中序遍历:n; InOrderTraverse(T); coutn后序遍历:n; PostOrderTraverse(T); break; case 3: if(!T) cout未建立树; else coutn先序遍历:n; NRPreOrder(T); coutn中序遍历:n; NRInOrder(T); coutn后序遍历:n; NRPostOrder(T); break; case 4:coutn层序遍历:n; LevelOrderTraverse(T); break; default: cout请确认选择项:n; /end switch /end while 4调试与操作说明4.1程序调试图4.1.1 调试界面在程序调试过程当中，编译时并没有报错，但是运行时总是出错，在查阅资料和老师的帮助下，发现创建二叉树的语句出现了问题。4.2程序操作说明（1）选择要执行的操作，第一步创建二叉树。按先序次序输入各结点的值，以#号表示空树。图4.2.1运行界面一（2）二叉树的递归遍历图4.2.2运行界面二（3）二叉树的非递归遍历图4.2.3运行界面三（4）二叉树的层次遍历图4.2.4运行界面四（5）退出图4.2.5运行界面五总 结通过这次的程序设计，我充分掌握了二叉树的一些基本算法，懂得了如何先序创建二叉树，二叉树的三种递归遍历算法，三种非递归遍历算法以及层次序遍历的算法。通过一周的课程设计，我已经会用先序次序完成二叉树的创建，对二叉树的多种遍历也有了更多、更广泛的理解。二叉树遍历的方法是构造各种二叉树操作的基础，有很多操作如果选用恰当的遍历方法可以简化实现。对于线性结构而言，遍历是一种基本的操作，而二叉树是一种非线性结构，每个结点可能不止一个直接后继，这样必须规定遍历的规则，按此规则遍历二叉树，最后得到二叉树结点的一个线性序列。因而，二叉树的结点存在关于这个关于这个线性序列的前驱和后继。在设计的过程中，我查阅了大量的资料，掌握理论知识的同时，也吸取了很多老师和同学的方法。一些理论的知识平时可能比较难以理解，但通过课程设计，让我们更主动的去理解，去查阅有关知识，从而掌握得更加透彻。致 谢 本次数据结构课程设计我从指导老师身上学到了很多东西，让我收获很多。老师们认真负责的工作态度，严谨的治学精神和深厚的理论水平都使我收益匪浅。无论在理论上还是在实践中，他们都给了我很大的帮助，使我得到很大的提高，排除了各种困难，这对于我以后的学习甚至工作都有一种巨大的帮助，在此感谢他耐心的辅导。同学们给予了我很多意见，这次我能顺利完成课程设计，少不了他们的帮助，在此向给予我帮助的同学说声谢谢。在撰写课程设计报告阶段，老师审阅我们的报告，而且提出了许多意见，如果没有他的指导，我们就不能较好的完成这次课题设计的任务。我还要感谢对我有所教导的老师，他们孜孜不倦的教诲不但让我和同学们学到了很多知识，而且让我掌握了动手实践学习的方法，还提供了这么好的实践机会，更教会了我做人处事的道理，在此表示感谢。同时，在编程过程中还有同学们给了我帮助和建议，这里一并表示感谢。参考文献1 殷人昆.数据结构：面向