《实验报告3 数据结构与算法 》由会员分享,可在线阅读,更多相关《实验报告3 数据结构与算法 (8页珍藏版)》请在金锄头文库上搜索。
1、实实 验验 报报 告告 课程名称课程名称 数据结构与算法数据结构与算法 实验学期实验学期 20152015 年年 春季春季 学期学期所在学院所在学院 交通科学与工程学院交通科学与工程学院 所属专业所属专业 交通信息与控制工程系交通信息与控制工程系 年级年级 20122012 专业班级专业班级 学生姓名学生姓名 学号学号 指导教师指导教师 实验最终成绩实验最终成绩 实验报告(三)实验报告(三)实验题目二叉树的基本操作及应用实验时间 2015 年 6 月 10 日实验地点B07-B214实验成绩实验性质应用性 设计性 综合性教师评阅: 实验目的明确; 操作步骤正确; 设计文稿(表格、程序、数据库、
2、网页)符合要求; 保存路径正确; 实验结果正确; 实验分析总结全面; 实验报告规范; 其他:评阅教师签名:一、实验目的一、实验目的1 熟悉二叉树的存储结构和对二叉树的基本操作。2 掌握对二叉树前序、中序、后序遍历操作的具体实现。3 学习利用递归方法编写对二叉树这种递归数据结构进行处理的算法。4 会应用二叉树的基本操作解决简单的实际问题二、实验内容和要求二、实验内容和要求( (说明算法的时间复杂度说明算法的时间复杂度) )1 基于二叉链表的存储格式,输入二叉树的先序序列,用*代表空节点,如ABD*CE*F*建立二叉树,然后中序遍历二叉树,输出节点的值。2 针对建好的二叉树,编写递归程序,求树中叶
3、子节点个数。3 针对建好的二叉树,编写递归程序,求二叉树的高度。4 针对建好的二叉树,试编写二叉树的前序非递归非递归遍历算法。三、主要设计思想与算法三、主要设计思想与算法 (此处不够可加页,或在反面书写)(此处不够可加页,或在反面书写)该实验主要包括一下几个函数,算法核心分别在各函数中。该实验主要包括一下几个函数,算法核心分别在各函数中。1.1.建立树的结构。建立树的结构。typedeftypedefstructstruct BiTNodeBiTNodechar element;Tree lchild,rchild;/B 数的基本结点输入输入 ABD*CE*F*ABD*CE*F* TreeTr
4、ee CreateBTree(void)/CreateBTree(void)/可以返回一个可以返回一个 TreeTree 指针指针Tree pTree;char val;scanf(“%c“,printf(“%c“,val);if(val=*|val=p) return NULL;/根据输入字符先序建树 else/*代表空pTree=(Tree)malloc(sizeof(struct BiTNode);if(pTree=NULL)printf(“内存分配失败!“);exit(-1);/防止程序不知道空间不够用了pTree-element=val;pTree-lchild=CreateBTre
5、e();pTree-rchild=CreateBTree();/递归,NLR 地创建结点returnreturn pTree;pTree;2.2.数叶结点个数数叶结点个数intint CountLeaf(TreeCountLeaf(Tree T)T)if(T=NULL)return 0;if(!T-lchild/两个儿子都空则说明是叶子,返回 1elsereturn CountLeaf(T-lchild)+CountLeaf(T-rchild);/数左右子树总共的叶结点 ;3.3. 数树的深度数树的深度intint CountLevel(TreeCountLevel(Tree T)T)if(!
6、T) return 0;elseintLeft=CountLevel(T-lchild);intRight=CountLevel(T-rchild);return 1+(LeftRight? Left:Right);/三目运算取最大;/最后数得树的最深层数,也是递归typedeftypedef structstructTree elementsMAXSIZE;/注意这里放的是指针int top;Stack;/这是一个用于装 Tree 指针的栈4.4. 这是用非递归实现先序遍历的这是用非递归实现先序遍历的voidvoid PreOrder(TreePreOrder(Tree T)T)Stack
7、S;Tree p;InitStack(/造一个栈待会儿用p=T; /用 p 指针来不断处理结点操作 while ( p|!IsEmpty(S)while(p)printf(“%c“,p-element);/只要不空则把 p 指的数据输出Push(p=p-lchild;/继续往左边找/一旦停下来说明找到了空结点,则开始往上一层的右边找一下if(!IsEmpty(S) ) /栈非空p=Pop(/退栈,找到刚才说的上一层p=p-rchild;/找右边了/只要 while 还循环说明没有遍历完,现在再一次从刚才的右边执行先序遍历;四、实验结果(设计文档、文稿存放路径,可以截图描述实验结果)四、实验结果
8、(设计文档、文稿存放路径,可以截图描述实验结果)#include#include “3.h“int main(void)/改主程序对应上图结果Tree pTree;int i,j;pTree=CreateBTree();/创建二叉树 pTreei=CountLeaf(pTree);printf(“There are %d leaves!“,i);/递归程序数叶节点j=CountLevel(pTree);printf(“There are %d levels!“,j);/递归程序数层数PreOrder(pTree);/按照前序遍历输出该书的元素return 0;五、实验分析总结五、实验分析总结本
9、次实验采用二叉树存储了一系列的字符串,通过函数本次实验采用二叉树存储了一系列的字符串,通过函数 TreeTree CreateBTree(void)CreateBTree(void)得到一个根据输入创建的二叉树结构,时间复杂度是得到一个根据输入创建的二叉树结构,时间复杂度是O O(n n) ;通过函数;通过函数 intint CountLeaf(TreeCountLeaf(Tree T)T)递归返回叶子个数,时间复杂度递归返回叶子个数,时间复杂度O(n)O(n);通过;通过 intint CountLevel(TreeCountLevel(Tree T)T)返回最深路径得到树的深度,时间复杂返
10、回最深路径得到树的深度,时间复杂度度 O O(n n) ;最后用;最后用 voidvoid PreOrder(TreePreOrder(Tree T)T)实现非递归写法的二叉树先序遍历,时间实现非递归写法的二叉树先序遍历,时间复杂度为复杂度为 O(n).O(n).综上所述,因为都是要遍历综上所述,因为都是要遍历 B B 数的每个节点,所以程序执行的时间长度数的每个节点,所以程序执行的时间长度和输入的字符串长度和输入的字符串长度 n n 是线性增长的。他们的时间复杂度都是是线性增长的。他们的时间复杂度都是 O(n).O(n).这次实验,我更深刻的理解了这次实验,我更深刻的理解了 B B 数的基本
11、性质如递归性,利用递归,我数的基本性质如递归性,利用递归,我们可以很方便的写出各种对树的操作;熟悉了创建树,遍历树的基本方法;们可以很方便的写出各种对树的操作;熟悉了创建树,遍历树的基本方法;体会了算法的代码实现细节。最后,特别是在用非递归方法实现遍历的函数体会了算法的代码实现细节。最后,特别是在用非递归方法实现遍历的函数中,我更加深刻的理解到了数是如何遍历的,以及递归是不断调用自己的本中,我更加深刻的理解到了数是如何遍历的,以及递归是不断调用自己的本质,而且不仅仅对质,而且不仅仅对 BTreeBTree 本身有运用,之前学习的栈也用于存储遍历的节点本身有运用,之前学习的栈也用于存储遍历的节点指针,所以数据结构的学习应该是一个融会贯通的过程,我在学习的过程中指针,所以数据结构的学习应该是一个融会贯通的过程,我在学习的过程中越来越有信心了。越来越有信心了。