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

1、计算机工程学院课程设计报告课程名称：数据结构课程设计设计题目：二叉树的算法院 系：计算机工程学院专 业：计算机科学与技术组 别：47学生姓名:姚燕 学 号：1101301231起止日期:起止年12月19日2011年12月26日指导教师：张亚红孙成富邱军林窦海洲1 需求分析1.1.1 课程设计题目、任务及要求 11.2 课程设计思想 11.3 软硬件运行环境及开发工具 12 概要设计2.2.1 各功能模块流程图 22.2 创建二叉树 22.3 二叉树的递归遍历算法（先、中、后） 22.3.1 先序遍历 22.3.2 中序遍历 22.3.3 后序遍历 22.4 二叉树的非递归遍历算法（前、中、后）

2、 32.4.1 非递归的先序遍历算法 32.4.2 非递归的中序遍历算法 32.4.3 非递归的后序遍历算法 32.5 层次序遍历 32.6 退出 33 详细设计和实现3.3.1 主要功能模块设计 33.2 主程序设计 44 调试与操作说明6.4.1 程序调试 64.2 程序操作说明 6总结 9 致谢 1.0.参考文献1.1.1 需求分析1.1 课程设计题目、任务及要求二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。要求：遍历的内容应是多样的。1.2 课程设计思想首先按先序次序建立一个二叉树，递归遍历，包括先序、中序、后序递归遍历。 三种不同次序

3、的遍历二叉树的递归算法的结构相似，只是访问结点及遍历左子树、 遍历右子树的先后次序不同而已。在递归执行过程中，先序遍历是每进入一层递归调用时先访问根结点，再依次向它的左、右子树递归调用。中序遍历是在从左子树递归调用退出时访问根结点，然后向它的右子树递归调用。后序遍历是在从左、右子树递归调用后，再访问根结点。把一个递归过程改为非递归过程一般需要利用栈，记录遍历时的回退路径。利用栈的先序遍历二叉树（非递归）：每次访问一个结点后，在向左子树遍历下去之前，利用这个栈记录该结点的右子女（如果有的话）结点的地址，以便在左子树退回时可以直接从栈顶取得右子树的根结点，继续右子树的先序遍历。利用栈的中序遍历二叉

4、树（非递归）：首先访问的是中序下的一个结点，它位于从根开始沿左子树链走到最左下角的结点，该结点的左子树指针为空。访问它的数据之后，再遍历该结点的右子树。此右子树又是二叉树，重复执行上面的过程，直到该子树遍历完。结束条件为：栈为空的同时遍历指针也为空。利用栈的后序遍历二叉树 （非递归）： 在遍历完左子树是还不能访问根结点，需要再遍历右子树。右子树遍历完后才访问根结点。所以在栈记录中必须注明刚才是在左子树还是右子树中。 ，在算法中首先使用栈暂存根结点地址，再向左子树遍历下去，此时根结点的tag=1。访问完左子树结点并退回时，还要遍历根的右子树，此时改根结点的tag=2.在从右子树中退出时才访问位于

5、栈顶的根结点的值o层次序遍历从二叉树的根结点开始，自上而下，自左向右分层依次访问树中的各个结点。访问二叉树的处理需要利用一个队列。在访问二叉树的某一层结点是， 把下一层结点指针预先记忆在队列中，利用队列安排逐层访问的次序。每访问一个结点时，将它的子女依次加到队列的队尾，然后再访问已在队列队头的结点。这样可以实现二叉树结点的按层访问。1.3 软硬件运行环境及开发工具Windows2000 以上操作系统、Microsoft Visual C+ 6.02概要设计2.1 各功能模块流程图图2.1.2主函数流程图（b）2.2 创建二叉树（1）定义二叉树结点值的类型为字符型。（2）结点个数不超过20个。（

6、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

7、 非递归的中序遍历算法(1)指针指向p 的左孩子结点。(2)从栈中弹出栈顶元素。(3)访问结点的数据域。(4)指针指向p 的右孩子结点。2.4.3 非递归的后序遍历算法bt 是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志一同入栈。首先将 bt 和标记 (为 1)入栈，遍历左子树；返回后，修改栈顶标记为2，遍历右子树；最后访问根结点。2.5 层次序遍历(1)访问该元素所指结点。(2)若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。2.6 退出3 详细设计和实现3.1 主

8、要功能模块设计程序主要设计了五个功能：首先是创建二叉树, 按先序次序输入，构造二叉链表表示的二叉树T， #表示空树。其余还有四个模块，包括：二叉树的递归遍历算法(先序、中序、后序)；层次序遍历；二叉树的非递归遍历算法(先序、中序、后序)；退出。主函数流程如下：开始输开始入一个数是Switch(0)否是Switch(1)否是Switch(2)否是Switch(3)否是Switch(4)否是default退出>建立二叉树二叉树的递归遍 历算法（先、中、 后）是二叉树的非递归 遍历算法（先、 中、后）层次遍历图3.1.1主函数流程图（a）3.2 主程序设计void main（）BiTree T

9、;T=NULL;int select;/cout<<”请按先序次序输入各结点的值，以#表示空树（输入时可连续输 入）:"<<endl;/ CreateBiTree（T）;while（1）cout<<"n请输入要执行的操作的序号：n”;cout<<"1.创建二叉树 n"cout<<”2.二叉树的递归遍历算法(前、中、后)n”;cout<<”3.二叉树的非递归遍历算法(前、中、后)n”;cout<<"4.二叉树的层次遍历算法"cout<<&qu

10、ot;n0.退出 n”;cin>>select;switch(select)case 0:return;case 1:cout<<”先序次序输入二叉树，以#表示空树(输入时可连续输 入 ):"<<endl;CreateBiTree(T);break;case 2:if(!T) cout<<" 未建立树"elsecout<<"n 先序遍历:n"PreOrderTraverse(T);cout<<"n 中序遍历:n"InOrderTraverse(T);co

11、ut<<"n 后序遍历:n"PostOrderTraverse(T);break;case 3:if(!T) cout<<" 未建立树"elsecout<<"n 先序遍历:n"NRPreOrder(T);cout<<"n 中序遍历:n"NRInOrder(T);cout<<"n 后序遍历:n"NRPostOrder(T);break;case 4:cout<<"n 层序遍历:n"LevelOrderTra

12、verse(T);break;default:cout<<”请确认选择项：n"14end switch /end while4调试与操作说明4.1程序调试"C： Frogra> Tileslici_050f_t Visual请胞人要执行的操作的序号；1赵建三攵枕一：的递归遍历算彷（可 二昆树的非递归遍历寓鼠.二叉树的层次遍历算法0 ,退出t前、札后）图4.1.1调试界面在程序调试过程当中，编译时并没有报错，但是运行时总是出错，在查阅资 料和老师的帮助下，发现创建二叉树的语句出现了问题。4.2程序操作说明（1）选择要执行的操作，第一步创建二叉树。按先序次序输

13、入各结点的值，以 #号表示空树。请跑人要执行的操作的芹号;工.刨建二叉利Z.二又杓的密归阑不算法（前、中,后）3二叉内的非递归扃历算法前、札后）4 .二叉料的层次漏不算困I .退±1先序次序输入二叉惆.以M表示空树工输入时可连续输入予：L23H4IUN信替K要神行的操作的序号;L.掰建二叉树心二具杓的解斤扁方算法（前.申.后）3二叉声的非魂归扁历算法匕前、轧 后）心二艮树的层次漏而算双退出图4.2.1运行界面一（2）二叉树的递归遍历*Cz Progz ul Fjl 1 cKj.crosoft TisuaJL StudioXiByr'i u j cct sA78B.iEtd&q

14、uot;接先序次序输入心结点的值.以丧手空村工商人时可连续输入”-鬓青 作历历遍 s遍制工 内 m啖也 柒r 骞 一 雪叉里尺山 选创二二二限先序遍历二2 3中序遍历i Z 1，后 K 遍rJT ：图4.2.2运行界面(3)二叉树的非递归遍历a， *C: Prograim FileslticKosof t Visual St图4.2.3运行界面三(4)二叉树的层次遍历A *C:Progra* FilesMiciosoft Visual Stu申、后) 中、后)图4.2.4运行界面四>后后、*中中'、前 :尊、 号1法 存SS 而覃方草 洞历遍历 >遍归遍 前归递次 递非层

15、不熨的由的 兵建又叉又出 二二二退 壬W;BJB1 .5.i 剪、 号I法 序； 的S历草 作历遍历 操遍归遍 的归递也 一非层 丸兄的的的 要二：gw 3人建叉叉叉出 2第二二二退 Erm(5)退出图4.2.5运行界面五总结通过这次的程序设计，我充分掌握了二叉树的一些基本算法，懂得了如何先序创建二叉树，二叉树的三种递归遍历算法，三种非递归遍历算法以及层次序遍历的算法。通过一周的课程设计，我已经会用先序次序完成二叉树的创建，对二叉树的多种遍历也有了更多、更广泛的理解。二叉树遍历的方法是构造各种二叉树操作的基础，有很多操作如果选用恰当的遍历方法可以简化实现。对于线性结构而言， 遍历是一种基本的操

16、作，而二叉树是一种非线性结构，每个结点可能不止一个直接后继，这样必须规定遍历的规则，按此规则遍历二叉树，最后得到二叉树结点的一个线性序列。因而， 二叉树的结点存在关于这个关于这个线性序列的前驱和后继。在设计的过程中，我查阅了大量的资料，掌握理论知识的同时，也吸取了很多老师和同学的方法。一些理论的知识平时可能比较难以理解，但通过课程设计，让我们更主动的去理解，去查阅有关知识，从而掌握得更加透彻。致谢本次数据结构课程设计我从指导老师身上学到了很多东西，让我收获很多。老师们认真负责的工作态度，严谨的治学精神和深厚的理论水平都使我收益匪浅。 无论在理论上还是在实践中，他们都给了我很大的帮助，使我得到很大的提高， 排除了各种困难，这对于我以后的学习甚至工作都有一种巨大的帮助，在此感谢他耐心的辅导。同学们给予了我很多意见，这次我能顺利完成课程设计，少不了他们的帮助，在此向给予我帮助的同学说声谢谢。在撰写课程设计报告阶段，老师审阅我们的报告，而且提出了许多意见，如果没有他的指导，我们就不能较好的完成这次课题设计的任务。我还要感谢对我有所教导的老师，他们孜孜不倦的教诲不但让我和同学们学到了很多知识，而且让我掌握了动手实践学习的方法，还提供了这么好的实践机会，更教会了我做人处