实验三二叉树基本操作与应用实验
第一篇：实验三 二叉树基本操作与应用实验
实验三
二叉树基本操作与应用实验
第三次实验主要包括两部分内容：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)树型数据结构不仅使各类实际应用问题到了一种有效解决途径，而且它也对计算机科学技术本身的发展起到了非常重要的作用，如在编译原理过程中的编码问题，使得编译系统提高了速度。
第二篇：实验8 二叉树的基本操作
实验8 二叉树的基本操作
班级: 学号:
一、题目
由数字序列生成二叉树 假设我们有这样的二叉树：
节点的元素(key)是正整数，且互不相同。可能给出这样一个虚拟的树更有利于理解输入。是的，我们的输入是上图的先序遍历；
即,要求根据1 3 0 2 0 0 4 5 0 0 0这样的输入，构造出一棵只含有正整数节点的二叉树。
【输入】
扩展的二叉树的先序遍历 【输出】
构造的简单树的节点个数 【样例输入】 3 0 2 0 0 4 5 0 0 0 【样例输出】
二、程序清单
三、程序调试过程中所出现的错误
四、运行结果（界面）：
五、心得体会
第三篇：实验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)//二叉树的层序遍历

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。