实验3 二叉树及其应用
实验目的
1.加深对二叉树的结构特性的理解；
2.熟练掌握二叉树的存储结构，特别是二叉链表类的描述及其实现方法；
3.熟练掌握二叉树的遍历算法原理及实现；
4.学会编写实现二叉树的各种算法；
5.掌握二叉树的应用方法。
实验学时：建议2~4学时
实验内容
内容1：二叉树及其操作
【问题描述】
设计二叉树的二叉链表类，操作主要有建二叉树、遍历二叉树、求该二叉树中、的结点个数等。
【基本要求】
（1）建立二叉树可用先序方式建立，也可根据二叉树的先序和中序序列建立。
（2）对二叉树的遍历可采用递归或非递归的算法。
【实现提示】
（1）二叉链表的结点结构描述
struct btnode{ // 定义结点类型
ElemType data; //数据域
btnode * lchild，* rchild; //左、右指针域/
}; // btnode
（2）可设计以下功能函数：
btnode* createbitree(); //建立二叉链表
void preorder(btnode* bt); //先序遍历二叉树
int sum(btnode* bt); //求二叉树中的结点个数
算法可用递归或非递归实现。
建立二叉树可用以下两种算法实现：
方案1：btnode * createBT ( ) //前序建树
{ bitree T; char ch;
cin >>ch ;
if(ch==’#’) return NULL; //二叉树为空
T=new BinTNode; //申请根结点
T->data=ch;
T->lchild=createBTpre(); //创建根的左子树
1
2
T->rchild=createBTpre(); //创建根的右子树 return T; }
方案2：btnode* createBT ( char *preorder, char *midorder) { //由前序preorder 和中序midorder 建树，返回根指针 if(strlen (preorder) ==0) return NULL; //空二叉树 T= new Node; //建立根结点 T->data=*preorder;
k=locate(midorder ， *preorder); //找根在中序中的位置 lmidorder=fetch(midorder,0,k); //左子树的中序 lpreorder =fetch(preorder,1,k); //左子树的前序 rmidorder=fetch(midorder,k+1); //右子树的中序 rpreorder =fetch(preorder, k+1); //右子树的前序 T->lchild=createBT (lmidorder , lpreorder);//建根的左子树 T->rchild=createBT(rmidorder , rpreorder); //建根的右子树 return T; }
int sum(btnode* bt) //求二叉树中的结点个数 { if(!bt) return 0; //二叉树为空
return sum(bt->lchild) + sum(bt->rchild) +1; }
【选做内容】
（1） 对二叉树进行层次遍历算法。
（2） 求二叉树的深度、宽度等操作。
（3） 复制二叉树，交换二叉树中左右子树的问题怎么实现? 内容2：哈夫曼编码/译码器
【问题描述】设字符集为26个英文字母，其出现频度如下表所示。
先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。
51 48 1 15 63 57 20 32 5 1 频度
z y x w v u t 字符
1 16
1
18
8
23
80
频度
p 21 f q
15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格
字符
【基本要求】
算法具有以下功能：
（1）CreateHuffmanTree：根据给定字符的出现频数，建立其哈夫曼树。
（2）Encoding：对给定的原字符串进行编码。
（3）Decoding：对给定的编码串进行译码（或解码）。
（4）ShowHuffmanTree：显示哈夫曼树
【实现提示】
（1）用户界面可设计成模拟菜单方式。
（2）原字符串及编码串可从键盘输入。
（3）生成Huffman树的步骤如下：
①由给定的n 个权值{w1, w2, …, wn}构成n棵二叉树的集合（即森林）F =
{ T1, T2, …, Tn }，其中每棵二叉树Ti 中只有一个带权为wi 的根结点，
其左右子树均空。
②在 F 中选取两棵根结点的权值最小的树做为左右子树构造一棵新的二叉
树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
③在F 中删去这两棵树，同时将新得到的二叉树加入F中。
④重复②和③, 直到 F 只含一棵树为止。
这棵树便是赫夫曼树。
【选做内容】
（1）字符的出现频数能否从指定文件中统计而得？
（2）对指定的文件进行编码/解码。
3。