1 / 52
文档名称:

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

格式:doc   大小:273KB   页数:52页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

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

上传人:AIOPIO 2021/1/15 文件大小:273 KB

下载得到文件列表

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

相关文档

文档介绍

文档介绍:《数据结构与数据库》
实验报告
实验题目
二叉树的基本操作及运算
学 院:化学与材料科学学院
专业班级:09级材料科学与工程系 PB0920603
姓 ﻩ名:李维谷
学 号:PB09206285  
邮 箱:
指导教师:贾伯琪
实验时间:2010年10月17日
需要分析
问题描述:
实现二叉树(包括二叉排序树)的建立,并实现先序、中序、后序和按层次遍历,计算叶子结点数、树的深度、树的宽度,求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目,以及二叉树常用运算。
问题分析:
二叉树树型结构是一类重要的非线性数据结构,对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义,所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题,我觉得应该:
建立二叉树;
通过递归方法来遍历(先序、中序和后序)二叉树;
通过队列应用来实现对二叉树的层次遍历;
借用递归方法对二叉树进行一些基本操作,如:求叶子数、树的深度宽度等;
运用广义表对二叉树进行广义表形式的打印。
算法规定:
输入形式:为了方便操作,规定二叉树的元素类型都为字符型,允许各种字符类型的输入,没有元素的结点以空格输入表示,并且本实验是以先序顺序输入的.
输出形式:通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印,.
程序功能:实现对二叉树的先序、中序和后序遍历,层次遍历。计算叶子结点数、树的深度、树的宽度,求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找,对二叉树的某个结点进行删除。
测试数据:输 入 一:ABC□□DE□G□□F□□□ (以□表示空格),查找5,删除E
   预测结果:先序遍历 ABCDEGF
ﻩﻩ   中序遍历 CBEGDFA
ﻩﻩﻩ   后序遍历 CGEFDBA
      层次遍历 ABCDEFG
               广义表打印 A(B(C,D(E(,G),F)))
               叶子数 3 深度 5 宽度 2 非空子孙数 6 度为2的数目 2 度为1的数目2
  查找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
             查找10,失败.
删除B后,以广义表形式打印A(,C(F(,G)))
概要设计
程序中将涉及下列两个抽象数据类型:一个是二叉树,一个是队列。
1、设定“二叉树"的抽象数据类型定义:
ADT BiTree{
ﻩ数据对象D:D是具有相同特性的数据元素的集合.
数据关系R:
 若,则,称BiTree为空二叉树;
  若,则,H是如下二元关系:
在D中存在唯一的称为根的数据元素root,它在关系H下无前驱;
若则存在且;
若则中存在唯一的元素,且存在上的关系若则中存在唯一的元素,且存在上的关系;
是一棵符合本定义的二叉树,称为根的左子树,是一棵符合本定义的二叉树,称为根的有字树
基本操作:
   CreateBiTree&T)
操作结果:按照T的定义构造一个二叉树。
     BiTreeDepth(& T)
初始条件:二叉树T已存在。
操作结果:返回T的深度。
BiTreeWidth(&T)
初始条件:二叉树T已存在。
操作结果:返回T的宽度。
PreOderTraverse&T)
    初始条件:二叉树T已存在。
      操作结果:先序遍历打印T,
InOderTraverse(&T)
初始条件:二叉树T已存在。
  操作结果:中序遍历打印T。
PostOderTrave

最近更新

2025年女性妇科疾病检查全攻略 30页

版国有土地使用权租赁合同(宗地租赁合同) 6页

2025年度生物科技研发与转让交易合同协议书 9页

2025年度生物技术研发免责与成果转化合同 9页

版公司战略合作法律顾问合同 6页

2025年度生态循环农业养殖合作意向书 9页

2025年医院感染防控技能提升培训 30页

2025年BIM技术在养老公寓成本控制与项目管理中.. 30页

2025年免疫学核心揭秘免疫系统与器官功能奥秘.. 27页

2025年度生态农业合伙入股种植合同 8页

2025年度生态保护区临时土地租赁及生态环境保.. 9页

2025年人心解析社会心理学奥秘 20页

2025年度环保项目中介服务合同模板 9页

2025年度环保设备制造员工自愿解除劳动合同协.. 7页

2025年度环保型清洁用品采购及保洁服务合同 9页

2025年个人健康记录管理 37页

2025年度特色课程培训学校品牌授权转让协议 8页

2025年度特色商业街区前期物业管理服务协议 8页

2025年度特种作物种植用地租赁合同范本 8页

2025年度物流园区前期物业管理服务合同 8页

2025年度物业门卫服务质量监控合同 8页

2025年度灾害预防工程外包安全协议 9页

2025年度深圳金融服务业劳动合同电子版规范文.. 8页

2025年度海洋工程设备全新安装合同及海洋环境.. 9页

2025年度海上风电场建设施工协议 9页

2025年度河北省房屋租赁及租期调整合同 8页

2025年度汽车维修保养委托协议合同 9页

2025年度汽车动产质押合同——汽车租赁公司车.. 8页

2025年度水利工程质保金监管与服务协议 8页

2025年安徽省初中学业水平考试名校联考(一)数.. 2页