《二叉树基本操作实验报告》

《二叉树基本操作实验报告》

ID:33960294

大小:270.50 KB

页数:27页

时间:2019-03-02

《二叉树基本操作实验报告》_第1页
《二叉树基本操作实验报告》_第2页
《二叉树基本操作实验报告》_第3页
《二叉树基本操作实验报告》_第4页
《二叉树基本操作实验报告》_第5页
资源描述:

《《二叉树基本操作实验报告》》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、e446270a103f8a658993f3b659f8ccda.doc《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算学院:化学与材料科学学院专业班级:09级材料科学与工程系PB0920603姓名:李维谷学号:PB09206285邮箱:liwg@mail.ustc.edu.cn指导教师:贾伯琪实验时间:2010年10月17日第27页共27页e446270a103f8a658993f3b659f8ccda.doc一、需要分析问题描述:实现二叉树(包括二叉排序树)的建立,并实现先序、中序、后序和按层次遍历,计算叶子结点数、树的深度、树的宽度,求树的非空子孙结点

2、个数、度为2的结点数目、度为2的结点数目,以及二叉树常用运算。问题分析:二叉树树型结构是一类重要的非线性数据结构,对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义,所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题,我觉得应该:1、建立二叉树;2、通过递归方法来遍历(先序、中序和后序)二叉树;3、通过队列应用来实现对二叉树的层次遍历;4、借用递归方法对二叉树进行一些基本操作,如:求叶子数、树的深度宽度等;5、运用广义表对二叉树进行广义表形式的打印。算法规定:输入形式:为了方便操作,规定二叉树的元素类型都为字符型,允许各种字符类型的输

3、入,没有元素的结点以空格输入表示,并且本实验是以先序顺序输入的。输出形式:通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印,再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。程序功能:实现对二叉树的先序、中序和后序遍历,层次遍历。计算叶子结点数、树的深度、树的宽度,求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找,对二叉树的某个结点进行删除。测试数据:输入一:ABC□□DE□G□□F□□□(以□表示空格),查找5,删除E预测结果:先序遍历ABCDEGF中序遍历CBEGDFA后序遍历CGEFDBA层次遍历ABCD

4、EFG广义表打印A(B(C,D(E(,G),F)))叶子数3深度5宽度2非空子孙数6度为2的数目2度为1的数目2第27页共27页e446270a103f8a658993f3b659f8ccda.doc查找5,成功,查找的元素为E删除E后,以广义表形式打印A(B(C,D(,F)))输入二:ABD□□EH□□□CF□G□□□(以□表示空格),查找10,删除B预测结果:先序遍历ABDEHCFG中序遍历DBHEAGFC后序遍历DHEBGFCA层次遍历ABCDEFHG广义表打印A(B(D,E(H)),C(F(,G)))叶子数3深度4宽度3非空子孙数7度为2的数目2度为1的数目3

5、查找10,失败。删除B后,以广义表形式打印A(,C(F(,G)))一、概要设计程序中将涉及下列两个抽象数据类型:一个是二叉树,一个是队列。1、设定“二叉树”的抽象数据类型定义:ADTBiTree{数据对象D:D是具有相同特性的数据元素的集合。数据关系R:若,则,称BiTree为空二叉树;若,则,H是如下二元关系:(1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱;(2)若则存在且;(3)若则中存在唯一的元素,且存在上的关系若则中存在唯一的元素,且存在上的关系;(4)是一棵符合本定义的二叉树,称为根的左子树,是一棵符合本定义的二叉树,称为根的有字树基本操

6、作:CreateBiTree&T)操作结果:按照T的定义构造一个二叉树。BiTreeDepth(&T)初始条件:二叉树T已存在。操作结果:返回T的深度。第27页共27页e446270a103f8a658993f3b659f8ccda.docBiTreeWidth(&T)初始条件:二叉树T已存在。操作结果:返回T的宽度。PreOderTraverse&T)初始条件:二叉树T已存在。操作结果:先序遍历打印T,InOderTraverse(&T)初始条件:二叉树T已存在。操作结果:中序遍历打印T。PostOderTraverse(&T)初始条件:二叉树T已存在。操作结果:后

7、序遍历打印T。LevelTraverse(&T)初始条件:二叉树T已存在。操作结果:层次遍历T。DeleteXTree(&T,TElemTypex)初始条件:二叉树已存在。操作结果:删除元素为x的结点以及其左子树和右子树。CopyTree(&T)初始条件:二叉树T已存在。操作结果:以T为模板,复制另一个二叉树。}ADTBiTree2、设定队列的抽象数据类型定义:ADTQueue{数据对象:D={数据关系:R1={<>

8、,,i=2,…,n}约定端为队列头,端为队列尾。基本操作:InitQueue(&Q)操作结果:构造一个空队列Q。EnQueue(&Q,

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。