【贪心算法】哈夫曼编码

《【贪心算法】哈夫曼编码》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、.cpp#include#include#include"huffmantree.h"intmain(intargc,char*argv[]){intweight,i=1,num;cout<<"num:"<>num;int*a=newint[num+1];a[0]=0;cout<<"array:"<>weight){if(weight==0)break;a[i++]=weight;}cout<huffman;huffman=HuffmanTr

2、ee(a,i-1);HuffmanEncode(huffman,i-1);huffman.PreOutput();return0;}huffmantree.h#include"binarytree.h"#include"MinHeap.h"#definelen10templateclassHuffman{friendBinaryTreeHuffmanTree(T[],int);public:operatorT()const{returnweight;}private:BinaryTreetree;Tweight;};templateBina

3、ryTreeHuffmanTree(Ta[],intn){Huffman*w=newHuffman[n+1];BinaryTreez,zero;for(inti=1;i<=n;i++){z.MakeTree(a[i],zero,zero);w[i].weight=a[i];w[i].tree=z;}MinHeap>H(1);H.Initialize(w,n,n);Huffmanx,y;for(i=1;i

4、);x.weight+=y.weight;x.tree=z;H.Insert(x);}H.DeleteMin(x);H.Deactivate();delete[]w;returnx.tree;}voidHuffmanEncode(BinaryTree&t,intn){intcode[len];inti=0,k=0;BinaryTreeNode*node=t.root;code[i++]=0;while(kLeftChild&&!node->LeftChild->visited){node->LeftChild->visited=true;code

5、[i++]=0;node=node->LeftChild;}elseif(node->RightChild&&!node->RightChild->visited){node->RightChild->visited=true;code[i++]=1;node=node->RightChild;}elseif(!(node->LeftChild

6、

7、node->RightChild)){cout<data<<"t:";for(intj=1;jParent;if(i<1)brea

8、k;i-=1;}else{node=node->Parent;if(i<1)break;i-=1;}}}binarytree.htemplateclassBinaryTree;templateclassBinaryTreeNode{friendvoidVisit(BinaryTreeNode*);friendvoidInOrder(BinaryTreeNode*);friendvoidPreOrder(BinaryTreeNode*);friendvoidPostOrder(BinaryTreeNode*);friendvoidLeve

9、lOrder(BinaryTreeNode*);friendintmain(intargc,char*argv[]);friendclassBinaryTree;friendBinaryTreeHuffmanTree(Ta[],intn);friendvoidHuffmanEncode(BinaryTree&t,intn);public:BinaryTreeNode(){Lef