2023年数据结构与算法实验报告新编.docx

《2023年数据结构与算法实验报告新编.docx》由会员分享，可在线阅读，更多相关《2023年数据结构与算法实验报告新编.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告课程名称数据结构与算法实验学期 .20 23 年.春季 学期所在学院 交通科学与工程学院.所属专业 . 交通信息与控制工程系年级2023专业班级学生姓名学号一指导教师 .一实验最终成绩实验报告（三）实验题目二叉树的基本操作及应用实验时间2023年6月10日实验地点B07-B214实验成绩实验性质口应用性 设计性 综合性教师评阅：实验目的明确；口操作环节对的；口设计文稿（表格、程序、数据库、网页）符合规定;保存途径对的；口实验结果对的；口实验分析总结全面；口实验报告规范；评阅教师署名：一、实验目的1熟悉二叉树的存储结构和对二叉树的基本操作。2掌握对二叉树前序、中序、后序遍历操作的具体实现

2、。3学习运用递归方法编写对二叉树这种递归数据结构进行解决的算法。4会应用二叉树的基本操作解决简朴的实际问题三、重要设计思想与算法(此处不够可加页，或在反面书写)该实验重要涉及一下几个函数,算法核心分别在各函数中。1 .建立树的结构。t ypedef s t ruct Bi TNode(dc h ar elcmen t ;T r ee Ichi 1 d, r c hi 1 d ;；B数的基本结点输入 AB D *CE*F*T r e e C r ea t eBTree( v oi d )/ / 可以返回一个T r ee 指针 Tree pTree；*cha r v a 1;s c anf (%c

3、, &.val);叩 rint f C%c ”，val);oif(val=* Hval=二 p) ret urn NU LL;根据输入字符先 序建树else*代表空0 (个Tree= (Tree) mal loc ( s izeof (st ruct BiTNode);i f ( p T ree=NULL) ( pri n t f (内存分派失败！”)；。 exit(-l ) ;/防止程序不知道空间不够用了 o 0pTree- e 1 emen t =va 1 ；Tree-lc h ild=Cre a t eBTree();ooPTree-rch il d=C reate BTreeO； 递归

4、，NLR 地仓 U建结点 dor e turn pTr e e;2 .数叶结点个数i n t Coun t Lea f (T r e e T) dif ( T =NUL L ) r e tur n 0； df(!T-lch ild&!T- r child)(-return 1;/两个儿子都空则说明是叶子，返回1e Ise(ret urn Count L e af (T- 1 ch ild) +Coun t Lea f (T-rch i 1 d );/ 数左右子树总共的叶结点)；3 .数树的深度i n t Coun tLe v el (Tree T)(if (!T) re t urn 0;els

5、e(4nt Lef t =Co u ntL e vel (T-1 c hild) ; in t Right=Cou n t Level (T- r c h ild);re t urn 1+(Le f t R i ght? Left： Right)； /三目运算取最大;最后数得树的最深层数，也是递归type d e f s t r u ct Tree eleme n t s MAXSIZE； /注意这里放的是指针int t op;S tack； /这是一个用于装Tree指针的栈4 .这是用非递归实现先序遍历的void PreOr d e r (Tree T)(Stack S;oT ree p ；

6、o I nitStack (&S);造一个栈待会儿用叩二T ;用p指针来不断解决结点操作whil e ( p | | H s Em p t y (S)(w h i le (p)33 oprintf ( %c, P e 1 ement);只要不空则把p指的数据输出 Push(&S, p) ;p=p-lchild； 继续往左边找。) / /一旦停下来说明找到了空结点，则开始往上一层的右边找一下 i f (! I sE mp t y(S)。(栈非空s叩二Pop (&S)； 退栈，找到刚才说的上一层p = pr c h ild； 找右边了3)。/只要while还循环说明没有遍历完,现在再一次从刚才的右

7、边执行 先序遍历)；四、实验结果（设计文档、文稿存放途径，可以截图描述实验结果）#i n c 1 u d e # i nelude 3. h int main(v o id) 改主程序相应上图结果0Tree pTree;i n t i , j ;pT re e =Crea t e B T r ee 0 ; / /创建二叉树 pTreei=C o un t Leaf(pTree);pr i n t f (There are 与 d leaves! ,i)： 递归程序数叶节点j=C o untLevel(p Tr e e);opri n tf ( There a re %d levels! ”,j

8、)； /递归程序数层数Pr e Ord e r( p Tr e e) ;/按照前序遍历输出该书的元素return 0；五、实验分析总结本次实验采用二叉树存储了一系列的字符串，通过函数Tree Creat e BTr ee(v。id)得到一个根据输入创建的二叉树结构，时间复杂度是0 (n)； 通过函数in t CountLeaf(Tree T)递归返回叶子个数,时间复杂度0 (n)； 通过int CountLevel (Tree T)返回最深途径得到树的深度，时间复杂 度 0(n)；;最后用void PreO r d er (T ree T)实现非递归写法的二叉树先序遍历， 时间复杂度为0(n)

9、.综上所述，由于都是要遍历B数的每个节点，所以程序执行的时间长度 和输入的字符串长度n是线性增长的。他们的时间复杂度都是0( n).这次实验，我更深刻的理解了 B数的基本性质如递归性，运用递归，我们 可以很方便的写出各种对树的操作；熟悉了创建树，遍历树的基本方法;体会 了算法的代码实现细节。最后，特别是在用非递归方法实现遍历的函数中，我 更加深刻的理解到了数是如何遍历的，以及递归是不断调用自己的本质，并 且不仅仅对BTree自身有运用，之前学习的栈也用于存储遍历的节点指针，所 以数据结构的学习应当是一个融会贯通的过程,我在学习的过程中越来越有 信心了。二、实验内容和规定（说明算法的时间复杂度）1基于二叉链表的存储格式,输入二叉树的先序序列,用* *代表空节点，如ABD*CE*F*建立二叉树，然后中序遍历二叉树，输出节点的值。2针对建好的二叉树，编写递归程序，求树中叶子节点个数。3针对建好的二叉树,编写递归程序,求二叉树的高度。4针对建好的二叉树，试编写二叉树的前序就瀚9遍历算法。