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

实验报告课程名称数据结构与算法实验学期.2023年.春季学期所在学院交通科学与工程学院.所属专业.交通信息与控制工程系年级2023专业班级学生姓名―学号一指导教师.•一实验最终成绩实验报告（三）实验题目二叉树的基本操作及应用实验时间2023年6月10日实验地点B07-B214实验成绩实验性质口应用性□设计性□综合性教师评阅：□实验目的明确；口操作环节对的；口设计文稿（表格、程序、数据库、网页）符合规定;□保存途径对的；口实验结果对的；口实验分析总结全面；口实验报告规范；□评阅教师署名：一、实验目的1熟悉二叉树的存储结构和对二叉树的基本操作。2掌握对二叉树前序、中序、后序遍历操作的具体实现。3学习运用递归方法编写对二叉树这种递归数据结构进行解决的算法。4会应用二叉树的基本操作解决简朴的实际问题三、重要设计思想与算法(此处不够可加页，或在反面书写)该实验重要涉及一下几个函数,算法核心分别在各函数中。.建立树的结构。typedefstructBiTNode(dcharelcment;TreeIchi1d,rchi1d;}；〃B数的基本结点输入ABD**CE**F***TreeCreateBTree(void)//可以返回一个Tree指针{TreepTree；*charva1;scanf("%c〃,&.val);叩rintfC%c”，val);oif(val=='*'Hval=二'…p')returnNULL;〃根据输入字符先序建树else〃*代表空0(个Tree=(Tree)malloc(sizeof(structBiTNode));if(pTree==NULL)(°printf("内存分派失败！”)；。exit(-l);//防止程序不知道空间不够用了o}0pTree->e1ement=va1；Tree->lchild=CreateBTree();ooPTree->rchild=CreateBTreeO；〃递归，NLR地仓U建结点doreturnpTree;.数叶结点个数intCountLeaf(TreeT){dif(T==NULL)return0；df(!T->lchild&&!T->rchild)(-return1;//两个儿子都空则说明是叶子，返回1}eIse(®returnCountLeaf(T->1child)+CountLeaf(T->rchi1d);//数左右子树总共的叶结点)}；.数树的深度intCountLevel(TreeT)(if(!T)return0;else(4ntLeft=CountLevel(T->1child);intRight=CountLevel(T->rchild);return1+(Left>Right?Left：Right)；//三目运算取最大}};〃最后数得树的最深层数，也是递归typedefstruct{Treeelements[MAXSIZE]；//注意这里放的是指针inttop;}Stack；//这是一个用于装Tree指针的栈.这是用非递归实现先序遍历的voidPreOrder(TreeT)(StackS;oTreep；oInitStack(&S);〃造一个栈待会儿用叩二T;〃用p指针来不断解决结点操作while(p||HsEmpty(S))(while(p)3{3oprintf("%c',P—>e1ement);〃只要不空则把p指的数据输出Push(&S,p);p=p->lchild；〃继续往左边找。)//一旦停下来说明找到了空结点，则开始往上一层的右边找一下if(!IsEmpty(S))。(〃栈非空s叩二Pop(&S)；〃退栈，找到刚才说的上一层p=p—>rchild；〃找右边了3)。}//只要while还循环说明没有遍历完,现在再一次从刚才的右边执行先序遍历)；四、实验结果（设计文档、文稿存放途径，可以截图描述实验结果）#inc1ude<stdio.h>#inelude"3.h"intmain(void)〃改主程序相应上图结果{0TreepTree;inti,j;®pTree=CreateBTree0;//创建二叉树pTree®i=CountLeaf(pTree);printf("Thereare与dleaves!",i)：〃递归程序数叶节点«j=CountLevel(pTree);oprintf("Thereare%dlevels!”,j)；//递归程序数层数°PreOrder(pTree);//按照前序遍历输出该书的元素return0；五、实验分析总结本次实验采用二叉树存储了一系列的字符串，通过函数TreeCreateBTree(v。id)得到一个根据输入创建的二叉树结构，时间复杂度是0(n)；通过函数intCountLeaf(TreeT)递归返回叶子个数,时间复杂度0(n)；通过intCountLevel(TreeT)返回最深途径得到树的深度，时间复杂度0(n)；;最后用voidPreOrder(TreeT)实现非递归写法的二叉树先序遍历，时间复杂度为0(n).综上所述，由于都是要遍历B数的每个节点，所以程序执行的时间长度和输入的字符串长度n是线性增长的。他们的时间复杂度都是0(n).这次实验，我更深刻的理解了B数的基本性质如递归性，运用递归，我们可以很方便的写出各种对树的操作；熟悉了创建树，遍历树的基本方法;体会了算法的代码实现细节。最后，特别是在用非递归方法实现遍历的函数中，我更加深刻的理解到了数是如何遍历的，以及递归是不断调用自己的本质，并且不仅仅对BTree自身有运用，之前学习的栈也用于存储遍历的节点指针，所以数据结构的学习应当是一个融会贯通的过程,我在学习的过程中越来越有信心了。二、实验内容和规定（说明算法的时间复杂度）1基于