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

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

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

第一部分 基本操作实验

[问题描述]

二叉树采用二叉链表作存储结构，试编程实现二叉树的如下基本操作 1．按先序序列构造一棵二叉链表表示的二叉树T；

2．对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点 的遍历序列；

3．求二叉树的深度，结点数目，叶结点数目； [数据描述]

／／二叉树的二叉链表存储表示

2 先序遍历二叉树递归算法

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

本文来源：https://www.bwwdw.com/article/phy6.html