数据结构C++使用最小堆实现huffman树
#pragma once
公司主营业务：网站建设、成都网站制作、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。成都创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联推出涉县免费做网站回馈大家。
#include"Heap.h"//使用博客实现的堆
template
struct HuffmanNode//节点的结构信息
{
T _weight;
HuffmanNode
HuffmanNode
HuffmanNode
HuffmanNode(const T& weight)
:_weight(weight)
, _parent(NULL)
, _left(NULL)
, _right(NULL)
{}
};
template
class HuffmanTree//huffman树的实现
{
typedef HuffmanNode
public:
HuffmanTree()
:_root(NULL)
{}
~HuffmanTree()
{
_Destroy(_root);
_root = NULL;
}
Node* GetRootNode()
{
return _root;
}
void CreateHuffmanTree(const T* array, size_t size, const T& invalid)
{
assert(array && size > 0);
struct Compare
{
bool operator()(Node*& l, Node*& r)
{
return (l->_weight < r->_weight);
}
};
////Heap
Heap
for (size_t i = 0; i < size; ++i)
{
if (array[i] != invalid)
{
Node* node = new Node(array[i]);
minHeap.Push(node);
}
}
if (minHeap.Empty())
return;
Node* parent = minHeap.GetTop();
while (minHeap.Size() > 1)
{
Node* first = minHeap.GetTop();
minHeap.Pop();
Node* second = minHeap.GetTop();
minHeap.Pop();
parent = new Node(first->_weight+second->_weight);
parent->_left = first;
parent->_right = second;
minHeap.Push(parent);
}
_root = parent;
}
void LevelOrder()
{
queue
if (_root == NULL)
return;
q.push(_root);
while (!q.empty())
{
Node* cur = q.front();
q.pop();
cout << cur->_weight << " ";
if (cur->_left)
q.push(cur->_left);
if (cur->_right)
q.push(cur->_right);
}
}
private:
void _Destroy(Node*& root)
{
if (root == NULL)
return;
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
root = NULL;
}
protected:
Node* _root;
};
void TestTree()
{
int ar[] = { 2, 3, 6, 0, 4, 5, 1, 9, 7, 8 };
//int ar[] = { 1,1,1,1,2,2 };
HuffmanTree
tree.CreateHuffmanTree(ar, sizeof(ar) / sizeof(ar[0]), -1);
tree.LevelOrder();
}
网站名称：数据结构C++使用最小堆实现huffman树
分享路径：http://scjbc.cn/article/pjgjsg.html
