树和哈夫曼树实验报告

哈夫曼树实验报告2011.4.22实验题目：Huffman编码和译码。实验目的：1、练习树和哈夫曼树的有关操作，和各个算法程序。2、理解哈夫曼树的编码和译码实验内容:抽象数据类型：ADTHuffmantree{数据对象:D={带有各自实数W(D)的数据元素}数据关系：(1)D=NULL则huffmantree不存在//判断huffman树是否存在(2)D≠NULLR={H}.H为如下二元关系：//如果存在，假设R为其元素名称，H为里边所有元素①D中存在唯一根数据元素root,这个元素无前驱。//如果只有一个元素，则为根元素②D-{root}≠NULL.则存在D-{root}={D1，Dr}.且D1∧Dr=NULL//如果除了根元素还有别的元素，那么会有D1和Dr两部分，并且两者的交集为空，也就是两者是独立的。③若D1≠NULL，则D1中存在唯一元素xr,<root,xr>∈H//如果D1部位空集，则会有一个元素xr，且存在Dr上关系Hr∈H,H={<root,x1>,<root,xr>,H1,Hr};④符合①②③的R的组合中，存在一个组合R’使D中所有结点到root长与其权值W(Di)相乘的和最小，此时的<D/R>集合称为huffmantree.基本操作：voidselect(HTNodeHT[],intm,int*s1,int*s2)//比较得到权最小的两棵树。用指针指向所在位置。*voidprint1(char*HC[])//将哈弗曼编码逐个打印出来voidprint2(HTNodeHT[])//将哈夫曼树前后的结构打印出来voidCreatHuffmanTree(HTNodeHT[],lettervaluew[])//建立哈夫曼树voidHuffmanTreeCoding(HTNodeHT[],char*HC[])//从树根出发，对哈夫曼树做一次先序遍历，在遍历过程中利用一个字符//的顺序栈S记下遍历路程，向左转时0入栈，向右转时1入栈。当遍历到//一个叶子节点时，栈s自栈底至栈顶记录着树根到该叶子结点的路径上的//0,1序列，即该叶子结点的哈弗曼编码。voiddecode(HTNodeHT[],lettervaluew[])//把编码译成哈夫曼码}ADTHuffmantree二、算法描述：建立哈夫曼树：对于给定的n个权值{W1，W2，…，Wn}，构成n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右子树均空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入到F中。重复(2)和(3)，直到F只含一棵树为止。这棵树便是带权路径长度WPL最小的赫夫曼树。

具体操作：（1）N个叶子节点赋节点值和权值，并将孩子，双亲的值置0。其余节点所有值置0。（2）从HT中选择两个权值最小且尚无父节点的节点构建新树，并完成对双亲，孩子信息的复值。（3)循环N-1次实现整个树的构建。求编码：从左到右扫描HT，若当前节点HT[i]有双亲，则将其双亲入栈，并将HT[i]是其双亲的左孩子或右孩子记录至flag数组。这样继续搜寻，一定可以最终找到根节点，而此时flag数组所记录的信息即为HT[i]所对应的Huffman编码。由于栈的先进后出性质，从栈中将其一一取出则正好是其对应的Huffman编码。每个HT[i]都可以用上述方法找到其对应的Huffman编码，故所有节点都可以用此方法做出。具体操作：（1）从叶子节点开始按照所储存的父节点的信息向上寻找，若该节点是父节点的左孩子将路径记为0，是右孩子则将路径记为1。（2）用临时字符数组cd来储存路径并从从后向前储存。（3）从1.找到的父节点开始继续向上寻找，直到找到根节点，即parent为0结束。（4)将整个路径copy到HC中。解码：具体操作：（1）以字符串的形式输入编码存于code中。（2）从根节点开始按照编码所给的路径一次向下寻找，即：code=1，访问右子树；code=0，访问左孩子。（3）直到找到叶子节点为止。径字符写入译码数组text。（4）此时，若code=’\0’，则译码结束；否则继续从根节点开始寻找，重复1-3。（5）打印译码。三、程序清单：（略）四、运行结果（截图）：五、调试分析和体会：1.生成Huffman树时，我们直接采用数组来做而舍弃指针，简化了编程复杂度，由其序列的稳定性我们可以正确无误地生成所对应的Huffman树。2．判断一个节点是否被用过时我们无须另开数组来表示，而直接利用其是否有双亲