实验2：二叉树、树及应用(必威体育精装版).docVIP

集美大学数据结构课程实验报告 课程名称：数据结构 班级：软件1373 实验成绩： 指导教师：吴晓晖 姓名：欧伟勇 实验项目：实验2：二叉树、树及应用 学号：201342059074 上机实践日期： 一、目的 二、内容 4．实现一个哈夫曼树 5．输出相应的哈夫曼编码并译码。（编程可选做） 设：A、B、C、D、E权重分别为7,5,2,4 ,3 要求对文本ADBACBEDACDAEBDBAEDAAB编码并译码。 请说明等长编码时，编码长度为多少，每个字符分别的编码，该文本的编码后的长度共多少？（必做） （1）等长编码 这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。 采用哈夫曼编码后的每个字符的编码分别是什么？文本的编码后的长度共多少（必做） 11 01 100 00 101 7*2+5*2+2*3+5*2+3*3=49 编码长度为3 每个字符分别的编码 A 000 B 001 C 010 D 011 E 100 F 101 该文本的编码长度为3*22=66 三、用环境 #include iostream #include binarytree.h using namespace std; int main() { binarytreechar P(#); binarytreechar P1(P); cout请输入一棵二叉树进行测试：endl; //用字符型测试ABC##DE#G##F##H## bintreenodechar* Q = P.getroot(); P.Createbintree(Q); cout 前序遍历为： endl; P.pretraverse(Q); coutendl; cout 中序遍历为： endl; P.intraverse(Q); coutendl; cout 后序遍历为： endl; P.posttraverse(Q); coutendl; cout endl 二叉树的节点个数为：; cout P.size(Q) endl; cout 二叉树深度为： P.height(Q) endl; cout 二叉树树种叶子数为： P.leaves(Q) endl; char current; cout请输入要查找父节点的某节点：endl; cincurrent; cout 节点current的父节点为：; bintreenodechar *node = P.parent(Q,current); if(node != NULL) cout node-date; else cout 不存在父节点！; coutendl; Bintree *T; T=CreateBinTree(); cout 非递归前序遍历为： endl; PreOrderTraversal(T); coutendl; cout 非递归中序遍历为： endl; InOrderTraversal(T); coutendl; cout 非递归后序遍历为： endl; PostOrderTraversal(T); coutendl; //cout 查找信息为： P.find(Q,G)-date endl; //if(P.equal(Q,Q)) //cout endl; //else // coutbd endl; return 0; } #include iostream #include math.h #include stdlib.h using namespace std; template typename T struct bintreenode { T date; bintreenodeT *leftchild,*rightchild; bintreenode() { leftchild = NULL; rightchild = NULL; } bintree