实验8 二叉树的基本操作

时间:2019-05-12 07:24:22下载本文作者:会员上传
简介:写写帮文库小编为你整理了多篇相关的《实验8 二叉树的基本操作》,但愿对你工作学习有帮助,当然你在写写帮文库还可以找到更多《实验8 二叉树的基本操作》。

第一篇:实验8 二叉树的基本操作

实验8 二叉树的基本操作

班级: 学号:

一、题目

由数字序列生成二叉树 假设我们有这样的二叉树:

节点的元素(key)是正整数,且互不相同。可能给出这样一个虚拟的树更有利于理解输入。是的,我们的输入是上图的先序遍历;

即,要求根据1 3 0 2 0 0 4 5 0 0 0这样的输入,构造出一棵只含有正整数节点的二叉树。

【输入】

扩展的二叉树的先序遍历 【输出】

构造的简单树的节点个数 【样例输入】 3 0 2 0 0 4 5 0 0 0 【样例输出】

二、程序清单

三、程序调试过程中所出现的错误

四、运行结果(界面):

五、心得体会

第二篇:实验三 二叉树基本操作与应用实验

实验三

二叉树基本操作与应用实验

第三次实验主要包括两部分内容:1.二叉树基本操作实验;2.二叉树应用—赫夫曼树与赫夫曼编码实验。基本操作包括存储结构建立和遍历算法,本文只给出部分参考程序,请大家尽量完成多数基本操作。

第一部分 基本操作实验

[问题描述] 二叉树采用二叉链表作存储结构,试编程实现二叉树的如下基本操作

1.按先序序列构造一棵二叉链表表示的二叉树T;

2.对这棵二叉树进行遍历:先序、中序、后序以及层次遍历序列,分别输出结点 的遍历序列;

3.求二叉树的深度,结点数目,叶结点数目; [数据描述] //二叉树的二叉链表存储表示 先序遍历二叉树递归算法

6.层次遍历二叉树的非递归算法

7.求二叉树的深度

[说明]

1.按先序次序输入二叉树中结点的值,用‘#’表示空树,对每一个结点应当确定其左右子树的值(为空时必须用特定的空字符占位),故执行此程序时,最好先在纸上画出你想建立的二叉树,每个结点的左右子树必须确定。若为空,则用特定字符标出,然后再按先序输入这棵二叉树的字符序列。

2.为了简化程序的书写量,以及程序的清晰性,对结点的访问以一条输出语句表示,若有更复杂的或多种访问,可以将结点的访问编写成函数,然后通过函数指针进行函数的调用。读者若有兴趣,可自行编写。

3.c语言函数参数传递,都是以“传值”的方式,故在设计函数时,必须注意参数的传递。若想通过函数修改实际参数的值,则必须用指针变量作参数。具体设计时;读者一定要把指针变量及指针变量指向的值等概念弄清楚。

4.完整参考程序只给出了部分遍历算法,对于其他算法,请读者参照示例,自行编程完成,以加深学习体会。对于二叉链表的建立也是如此,示例中只是给出了先序法建立过程,读者可自行练习中序、后序二叉链表建立法,叶子结点或二叉树结点总数求法等。

第二部分 二叉树应用实验

---------郝夫曼树与郝夫曼编码

[问题描述] 利用HuffMan编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接受端将传来的数据编码进行译码(复原)。对于有些信道,每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个Huffman的编/译码系统。给定一组权值{7,9,5,6,10,l,13,15,4,8}.构造一棵赫夫曼树,并计算带权路径长度WPL。

Huffman编码存在磁盘文件中。提出这些要求,是给读者一定的思考空间和提高自己的编程能力的机会。读者需要注意类c语言描述的算法在转变为C源程序时关于函数参数的处理以及其他变量的定义与使用方法。

2.读者可参考此程序,实现Huffman编/译码系统的其他算法,以进一步加深理解和体会。

心得体会

(1)通信领域的编码问题曾经对许多的通信技术专家形成了困扰,后来人们对树型数据结构有了一定的认识之后,才有效地解决了通信的编码需求。它不仅使通信编码的长度缩短,更实际的意义是使整个电文的长度大大缩短了,从而迅速地提高了通信的效率。

(2)树型数据结构不仅使各类实际应用问题找到了一种有效解决途径,而且它也对计算机科学技术本身的发展起到了非常重要的作用,如在编译原理过程中的编码问题,使得编译系统提高了速度。

第三篇:实验3 - 二叉树的建立及基本操作

实验三

实验目的:

二叉树的建立及基本操作

本次实验的主要目的是熟练掌握二叉树的定义、三序(先序、中序、后序)遍历方法,并用遍历思想求解具体二叉树应用问题。通过程序实现,体会递归算法的优缺点。

实验要求:

用C语言编程实现二叉树的基本操作,并完成下述函数功能:(1)CreateBiTree():根据先序遍历序列生成一棵二叉树(2)Depth():求此二叉树的深度

(3)CountLeaf():统计该二叉树中叶子结点的个数(4)InOrderTraverse():中序遍历二叉树(5)PostOrderTraverse():后序遍历二叉树

在主函数main()中调用各个子函数完成单链表的基本操作。例: void main(){ BiTree T;CreateBiTree(T);int d= Depth(T);printf(“深度为%d”, d);int num= CountLeaf(T);printf(“叶子结点个数为%d”, num);InOrderTraverse(T);PostOrderTraverse(T);} //注意函数调用时,只传递参数名称,不需要传递参数类型和&符号。

[实现提示] 采用特殊符号,如*号表示空树的情况。

通过输入扩展的先序序列建立一棵二叉树,即,二叉树中结点为空时应输入*符号表示。[测试数据] 由学生自己确定,注意边界数据。

程序检查时,由老师提供用于建树的初始输入序列。

程序源码:(后付纸)程序运行结果:

实验心得体会:

有一些概念不明白,看书之后弄懂了,仔细看了二叉树遍历的知识点,问了同学有了思路。熟悉了二叉树的基本操作,掌握了二叉树实现。

第四篇:实验10 二叉树的基本操作

浙江大学城市学院实验报告

课程名称

数据结构基础

实验项目名称

实验十

二叉树的基本操作

实验成绩

指导老师(签名)

日期

一.实验目的和要求

1、掌握二叉树的链式存储结构。

2、掌握在二叉链表上的二叉树操作的实现原理与方法。

3、进一步掌握递归算法的设计方法。

二.实验内容

1、按照下面二叉树二叉链表的存储表示,编写头文件binary_tree.h,实现二叉链表的定义与基本操作实现函数;编写主函数文件test4_1.cpp,验证头文件中各个操作。

二叉树二叉链表存储表示如下: struct BTreeNode {

ElemType data;

// 结点值域

BTreeNode *lchild , *rchild;// 定义左右孩子指针 };基本操作如下:

①void InitBTree(BTreeNode *&BT);

//初始化二叉树BT

②void CreateBTree(BTreeNode *&BT, char *a);

//根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构

③int EmptyBTree(BTreeNode *BT);

//检查二叉树BT是否为空,空返回1,否则返回0 ④int DepthBTree(BTreeNode *BT);//求二叉树BT的深度并返回该值

⑤int FindBTree(BTreeNode *BT, ElemType x);

//查找二叉树BT中值为x的结点,若查找成功返回1,否则返回0

⑥void PreOrder(BTreeNode *BT);//先序遍历二叉树BT ⑦void InOrder(BTreeNode *BT);//中序遍历二叉树BT ⑧void PostOrder(BTreeNode *BT);

//后序遍历发二叉树BT

⑨void PrintBTree(BTreeNode *BT);

//输出二叉树BT ⑩void ClearBTree(BTreeNode *&BT);

//清除二叉树BT

2、选做:实现以下说明的操作函数,要求把函数添加到头文件binary_tree.h中,并在主函数文件test4_1.cpp中添加相应语句进行测试。①void LevelOrder(BTreeNode *BT)//二叉树的层序遍历

②int Get_Sub_Depth(BTreeNode *T , ElemType x)//求二叉树中以元素值为x的结点为根的子树的深度

3、填写实验报告,实验报告文件取名为report10.doc。

4、上传实验报告文件report10.doc、源程序文件test4_1.cpp及binary_tree.h到Ftp服务器上自己的文件夹下。

三.函数的功能说明及算法思路

(包括每个函数的功能说明,及一些重要函数的算法实现思路)函数:void InitBTree(BTreeNode *&BT)功能:初始化二叉树BT 思路:将BT指向NULL

函数:void CBTree(BTreeNode *&BT)功能:输入二叉树

思路:按先序次序输入二叉树中结点的值(一个字符)特殊字符 $ 表示空树

函数:void PBTree(BTreeNode *BT,int n)功能:横向打印二叉树

思路:先递归输出右子树,按层次输出空格和“---”控制格式,再输出当前结点值,最后递归左子树

函数:void CreateBTree(BTreeNode *&BT, char *a)功能:根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构

思路:根据广义表表示的”(”,”)”和”,”等字符来构建二叉树,用栈S来存储根结点指针,用p来接收当前结点值数据并链接为栈顶元素的左/右孩子

函数:int EmptyBTree(BTreeNode *BT)功能:检查二叉树BT是否为空,空返回1,否则返回0 思路:返回判断BT是否指向NULL

函数:int DepthBTree(BTreeNode *BT)功能:求二叉树BT的深度并返回该值

思路:若一棵二叉树为空,则它的深度为0,否则它的深度等于左子树和右子树中的最大深度加1

函数:int FindBTree(BTreeNode *BT, ElemType x)功能:查找二叉树BT中值为x的结点,若查找成功返回1,否则返回0

思路:类似于前序遍历,若空树则返回0。若根结点值等于查找值x则返回1,否则先调用函数本身查找左子树,还未找到则再查找右子树,所有操作完成均为找到,则返回0

函数:void PreOrder(BTreeNode *BT)功能:先序遍历二叉树BT 思路:使用“根左右”的顺序遍历二叉树

函数:void InOrder(BTreeNode *BT)功能:中序遍历二叉树BT 思路:使用“左根右”的顺序遍历二叉树

函数:void PostOrder(BTreeNode *BT)

功能:后序遍历二叉树BT 思路:使用“左右根”的顺序遍历二叉树

函数:void PrintBTree(BTreeNode *BT)

功能:输出二叉树BT 思路:按照广义表表示方法输出二叉树(与输入时相同)

函数:void ClearBTree(BTreeNode *&BT)

功能:清除二叉树BT 思路:按照先子树后根结点的顺序删除二叉树

函数(选作):void LevelOrder(BTreeNode *BT)功能:二叉树的层序遍历

思路:初始化一个空队列,若二叉树为空,则空操作;否则,树根指针入队列。当队列非空时循环:出队首元素,并输出该元素(指针)所指结点的值;且若该结点存在左右孩子,则左右孩子指针进队列。输出结果就是层序遍历序列

函数(选作):求二叉树中以元素值为x的结点为根的子树的深度 功能:int Get_Sub_Depth(BTreeNode *T , ElemType x)思路:在FindBTree函数的基础上修改,将找到结点时的返回值改为调用DepthBTree求出以该结点为根结点的子树深度即可

四.实验结果与分析

(包括运行结果截图、结果分析等)

测试数据:a(b(c),d(e(f,g),h(,i))),abc$$$def$$g$$h$i$$ 结果分析:针对该二叉树,程序输出深度为4,正确;查找值f能够找到,正确;先序遍历结果为a b c d e f g h i,正确;中序遍历结果为c b a f e g d h i,正确;后续遍历结果为c b f g e I h d a,正确;输出二叉树的结果与输入一致,正确;使用先序输入二叉树和横向输出部分正确。选作部分,层序遍历结果为a b d c e h f g i,正确;以结点d为根结点的子树深度为3,正确。

五.心得体会

(记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。)

【附录----源程序】

第五篇:实验5_二叉树

赣南师范大学数学与计算机科学学院

实 验 报 告 册

课程名称:算法与数据结构

实验项目名称: 实验5.二叉树 实验学时: 4 学生学号与姓名: 实验地点: 数计楼四楼 实验日期: 年 月 日 指导老师:

实验5 二叉树

一、实验目的和要求

(1)掌握二叉树的生成,以及前、中、后序遍历算法。(2)掌握应用二叉树递归遍历思想解决问题的方法。

二、实验仪器和设备

Visual C++ 6.0

三、实验内容与过程

1.建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历,输出遍历序列。

2.在第一题基础上,求二叉树中叶结点的个数。3.在第一题基础上,求二叉树的深度。

程序清单: 1.2.3.赣南师范大学数学与计算机科学学院

四、实验结果与分析(程序运行结果及其分析)

五、实验体会(遇到问题及解决办法,编程后的心得体会)

下载实验8 二叉树的基本操作word格式文档
下载实验8 二叉树的基本操作.doc
将本文档下载到自己电脑,方便修改和收藏,请勿使用迅雷等下载。
点此处下载文档

文档为doc格式


声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:645879355@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。

相关范文推荐

    第四次实验--二叉树遍历

    一、 二叉链表的声明 .BinaryNode public class BinaryNode //二叉树的二叉链表结点类,泛型T指//定结点的元素类型 { public T data; //数据域,存储数据元素 public BinaryNod......

    初中化学基本实验操作总结

    一、初中化学实验常用仪器和药品的取用规则 (一)初中化学实验常用仪器 1、试管 (1)用途: a、在常温或加热时,用作少量试剂的反应容器 b、溶解少量固体 c、收集少量气体 (2)注意事项......

    物理实验基本操作小结

    初中物理实验基本操作小结 1、三个"零" 1.1 天平调零前,游码应放在横梁的零刻度处。 1.2 使用弹簧秤、电压表、电流表、欧姆表时要检查指针是否在零刻度处。 1.3 一切非零数字和......

    数据结构二叉树操作验证实验报告

    班级:计算机11-2 学号:40 姓名:朱报龙成绩:_________ 实验七 二叉树操作验证 一、 实验目的 ⑴ 掌握二叉树的逻辑结构; ⑵ 掌握二叉树的二叉链表存储结构; ⑶ 掌握基于二叉链表......

    数据结构课程设计-_平衡二叉树操作 - 副本

    课 程 设 计 报 告 一. 需求分析 1、建立平衡二叉树并进行创建、增加、删除、调平等操作。 2、设计一个实现平衡二叉树的程序,可进行创建、增加、删除、调平等操作,实现动态的......

    数据结构课程设计-平衡二叉树操作

    课 程 设 计 报 告 课程名称 数据结构课程设计 题 目平衡二叉树操作 指导教师 设计起止日 2010-5-16 学 院 计算机学院 专 业软件工程 学生姓名 班级/学号------------......

    初三化学--化学实验基本操作二

    和被称量的物质颠倒了,此时该物质的实际质量应是() A.7.9gB.8.0gC.8.1gD.8.3g 2、某学生用量筒量取液体时,量筒放平稳后俯视液面读数为19ml,倾倒部课题:化学实验基本操作二执笔人: 赵......

    实验7 网络的基本操作

    注意: 本次实验完成后把最后两页实验报告打印成纸质文档,下次上理论课时上交。其中,[实验内容]的蓝色文字部分是实验报告2答题纸所填写内容 实验七、网络的基本操作 班级 学号......