实验2：二叉树、树及应用(最新)

《实验2：二叉树、树及应用(最新)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、集美大学数握结构课程实验报告课程名称：数据结构班级:软件1373实验成绩：指导教师：吴晓晖姓名：欧伟勇实验项目：实验2:二叉树、树及应用学号：201342059074上机实践日期:一、目的二义树数据结构及应用堆及其应用最优树及应用二、实验内容1.定义双叉链表的二叉树的数据结构（包括结构及基本操作）。（注：附屮有部分源码，及进一步的完成要求）2.定义最小堆及其数据结构，测试（1）采用数组53,17,78,9,45,65,87,23生成堆。（2）插入11，（2）删除9（注附中有部分源码及进一步的完成要求）3.采用堆实现优先级队列，完成

2、优先级队列的入队（即添加至堆尾，调整为堆）与出队（删除根，再调整为堆）。采用如下入队顺序实现测试：53,17,78,9,45,65,87,23。4.实现一个哈夫曼树5.输出相应的哈夫曼编码并译码。（编程可选做）设.•A、B、C、D、E权重分别为7,5,2,4,3要求对文本ADBACBEDACDAEBDBAEDAAB编码并译码。请说明等长编码时，编码长度为多少，每个字符分别的编码，该文本的编码后的长度共多少？（必做）（1）等长编码这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。假设字符集只含有4个

3、字符A，B，C，D，用二进制两位表示的编码分别为00,01,10,11。若现在有一段电文为：ABACCDA,则应发送二进制序列：00010010101100,总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。采用哈夫曼编码后的每个字符的编码分别是什么？文本的编码后的长度共多少（必做）1101100001017*2+5*2+2*3+5*2+3*3=49编码长度为3每个字符分别的编码A000B001C010DOilE100F101该文本的编码长度为3*22=6

4、6三、实验使用环境VC++6.0控制台程序四、实验关键代码与结果展示（部分截图）1.#include〈iostream〉#include"binarytree.h”usingnamespacestd;intmain(){binarytreeP(’#’)；binarytreeP1(P);^岀《”请输入一棵二叉树进行测试："«endl;//用字符型测试ABC##DE#G##F##H##bintreenode

5、<

6、父节点的某节点：’’<*node=P.parent(Q，current);if(node!=NULL)cout«node-〉date;elsecout«"不存在父节点！"；cout«endl;Bintree*T;T=CreateBinTree();cout«"非递归前序遍历为：’’<

7、derTraversal(T);cout«endl;cout«"非递归后序遍历为：’’<date«endl;//if(P.equal(Q,Q))//cout«n”《endl;//else//cout«"bdn«endl;return0;}#include#include#includeusingnamespacestd;template<

8、typenameT>structbintreenode{Tdate;bintreenode*leftchild，*rightchild;bintreenode(){leftchild=NULL;rightchild=NULL;}bintree