实验三 二叉树基本操作与应用实验
第三次实验主要包括两部分内容：1.二叉树基本操作实验；2.二叉树应用—赫夫曼树与赫夫曼编码实验。基本操作包括存储结构建立和遍历算法，本文只给出部分参考程序，请大家尽量完成多数基本操作。
第一部分 基本操作实验
[问题描述]
二叉树采用二叉链表作存储结构，试编程实现二叉树的如下基本操作 1．按先序序列构造一棵二叉链表表示的二叉树T；
2．对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点 的遍历序列；
3．求二叉树的深度，结点数目，叶结点数目； [数据描述]
／／二叉树的二叉链表存储表示
2 先序遍历二叉树递归算法
6. 层次遍历二叉树的非递归算法
7. 求二叉树的深度
[说明] 1．按先序次序输入二叉树中结点的值，用‘#’表示空树，对每一个结点应当确定其左右子树的值(为空时必须用特定的空字符占位)，故执行此程序时，最好先在纸上画出你想建立的二叉树，每个结点的左右子树必须确定。若为空，则用特定字符标出，然后再按先序输入这棵二叉树的字符序列。
2．为了简化程序的书写量，以及程序的清晰性，对结点的访问以一条输出语句表示，若有更复杂的或多种访问，可以将结点的访问编写成函数，然后通过函数指针进行函数的调用。读者若有兴趣，可自行编写。
3．c语言函数参数传递，都是以“传值”的方式，故在设计函数时，必须注意参数的传递。若想通过函数修改实际参数的值，则必须用指针变量作参数。具体设计时；读者一定要把指针变量及指针变量指向的值等概念弄清楚。
4．完整参考程序只给出了部分遍历算法，对于其他算法，请读者参照示例，自行编程完成，以加深学习体会。对于二叉链表的建立也是如此，示例中只是给出了先序法建立过程，读者可自行练习中序、后序二叉链表建立法，叶子结点或二叉树结点总数求法等。
第二部分 二叉树应用实验
---------郝夫曼树与郝夫曼编码
[问题描述]
利用HuffMan编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要