博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
哈夫曼树
阅读量:6582 次
发布时间:2019-06-24

本文共 4934 字,大约阅读时间需要 16 分钟。

BinTreeNode.h

 

template
class BinaryTree;template
void Huffman(Type *, int, BinaryTree
&);template
class BinTreeNode{public: friend class BinaryTree
; friend void Huffman
(Type *, int, BinaryTree
&); BinTreeNode():m_pleft(NULL),m_pright(NULL){} BinTreeNode(Type item,BinTreeNode
*left=NULL,BinTreeNode
*right=NULL) :m_data(item),m_pleft(left),m_pright(right){} void Destroy(){ //destroy the tree with the root of the node if(this!=NULL){ this->m_pleft->Destroy(); this->m_pright->Destroy(); delete this; } } Type GetData(){ return m_data; } BinTreeNode
*Copy(const BinTreeNode
*copy); //copy the nodeprivate: BinTreeNode
*m_pleft,*m_pright; Type m_data;};template
BinTreeNode
* BinTreeNode
::Copy(const BinTreeNode
*copy){ if(copy==NULL){ return NULL; } BinTreeNode
*temp=new BinTreeNode
(copy->m_data); temp->m_pleft=Copy(copy->m_pleft); temp->m_pright=Copy(copy->m_pright); return temp;}
BinaryTree.h
#include "BinTreeNode.h"template
void Huffman(Type *, int, BinaryTree
&);template
class BinaryTree{public: BinaryTree(BinaryTree
&bt1, BinaryTree
&bt2){ m_proot = new BinTreeNode
(bt1.m_proot->m_data + bt2.m_proot->m_data, bt1.m_proot, bt2.m_proot); } BinaryTree(Type item){ m_proot = new BinTreeNode
(item); } BinaryTree(const BinaryTree
©){ this->m_proot = copy.m_proot; } BinaryTree(){ m_proot = NULL; } void Destroy(){ m_proot->Destroy(); } ~BinaryTree(){// m_proot->Destroy(); } BinaryTree
& operator=(BinaryTree
copy); //evaluate node friend void Huffman
(Type *, int, BinaryTree
&); friend bool operator <
(BinaryTree
&l, BinaryTree
& r); friend bool operator >
(BinaryTree
&l, BinaryTree
& r); friend bool operator <=
(BinaryTree
&l, BinaryTree
& r); friend ostream& operator<<
(ostream& ,BinaryTree
&); //output the dataprivate: BinTreeNode
*m_proot; void Print(BinTreeNode
*start,int n=0); //print the tree with the root of start};template
bool operator <(BinaryTree
&l, BinaryTree
&r){ return l.m_proot->GetData() < r.m_proot->GetData();}template
bool operator >(BinaryTree
&l, BinaryTree
&r){ return l.m_proot->GetData() > r.m_proot->GetData();}template
bool operator <=(BinaryTree
&l, BinaryTree
&r){ return l.m_proot->GetData() <= r.m_proot->GetData();}template
void BinaryTree
::Print(BinTreeNode
*start, int n){ if(start==NULL){ for(int i=0;i
m_pright,n+1); //print the right subtree for(int i=0;i
=0){ cout<
m_data<<"--->"<
m_pleft,n+1); //print the left subtree}template
ostream& operator<<(ostream& os,BinaryTree
& out){ out.Print(out.m_proot); return os;}template
BinaryTree
& BinaryTree
::operator=(BinaryTree
copy){ m_proot=m_proot->Copy(copy.m_proot); return *this;}
MinHeap.h
template
class MinHeap{public: MinHeap(Type heap[],int n); //initialize heap by a array ~MinHeap(){ delete[] m_pheap; }public: bool Insert(const Type item); bool DeleteMin(Type &first);private: void Adjust(const int start, const int end); //adjust the elements from start to endprivate: const int m_nMaxSize; Type *m_pheap; int m_ncurrentsize;};template
void MinHeap
::Adjust(const int start, const int end){ int i = start,j = i*2+1; Type temp=m_pheap[i]; while(j <= end){ if(j
m_pheap[j+1]){ j++; } if(temp <= m_pheap[j]){ break; } else{ m_pheap[i] = m_pheap[j]; i = j; j = 2*i+1; } } m_pheap[i] = temp;}template
MinHeap
::MinHeap(Type heap[], int n):m_nMaxSize(n){ m_pheap = new Type[m_nMaxSize]; for(int i=0; i
=0){ Adjust(pos, n-1); pos--; }}template
bool MinHeap
::DeleteMin(Type &first){ first = m_pheap[0]; m_pheap[0] = m_pheap[m_ncurrentsize-1]; m_ncurrentsize--; Adjust(0, m_ncurrentsize-1); return 1;}template
bool MinHeap
::Insert(const Type item){ if(m_ncurrentsize == m_nMaxSize){ cerr<<"Heap Full!"<
0){ if(m_pheap[i] <= temp){ break; } else{ m_pheap[j] = m_pheap[i]; j = i; i = (j-1)/2; } } m_pheap[j] = temp; m_ncurrentsize++; return 1;}
Huffman.h
#include "BinaryTree.h"#include "MinHeap.h"template
void Huffman(Type *elements, int n, BinaryTree
&tree){ BinaryTree
first, second; BinaryTree
node[20]; for (int i=0; i
(elements[i]); } MinHeap
> heap(node, n); for (int i=0; i
GetData() == second.m_proot->GetData()){ tree = *(new BinaryTree
(second, first)); } else { tree = *(new BinaryTree
(first, second)); } heap.Insert(tree); }}
Test.cpp
#include 
using namespace std;#include "Huffman.h"int main(){ BinaryTree
tree; int init[10]={3,6,0,2,8,4,9,1,5,7}; Huffman(init,10,tree); cout << tree; tree.Destroy(); return 0;}

转载地址:http://pisno.baihongyu.com/

你可能感兴趣的文章
JQuery的ajaxFileUpload的使用
查看>>
关于Integer类中parseInt()和valueOf()方法的区别以及int和String类性的转换.以及String类valueOf()方法...
查看>>
ios 控制器的生命周期
查看>>
JavaScript 特殊效果代码
查看>>
【?】codeforces721E Road to Home(DP+单调队列)
查看>>
MySQL 仅保留7天、一个月数据
查看>>
Diff Two Arrays
查看>>
下拉菜单
查看>>
[清华集训2014]玛里苟斯
查看>>
Project Euler 345: Matrix Sum
查看>>
你可能不知道的技术细节:存储过程参数传递的影响
查看>>
.htaccess 基础教程(四)Apache RewriteCond 规则参数
查看>>
UVM中的class--2
查看>>
ORACLE 存储过程异常捕获并抛出
查看>>
root用户重置其他密码
查看>>
Oracle推断值为非数字
查看>>
多年前写的一个ASP.NET网站管理系统,到现在有些公司在用
查看>>
vue-cli中理不清的assetsSubDirectory 和 assetsPublicPath
查看>>
从JDK源码角度看Short
查看>>
五年 Web 开发者 star 的 github 整理说明
查看>>