#pragma once

公司主營業(yè)務(wù)：網(wǎng)站建設(shè)、成都網(wǎng)站制作、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。成都創(chuàng)新互聯(lián)是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。成都創(chuàng)新互聯(lián)推出涉縣免費做網(wǎng)站回饋大家。

#include"Heap.h"http://使用博客實現(xiàn)的堆

template

struct HuffmanNode//節(jié)點的結(jié)構(gòu)信息

{

T _weight;

HuffmanNode* _parent;

HuffmanNode* _left;

HuffmanNode* _right;

HuffmanNode(const T& weight)

:_weight(weight)

, _parent(NULL)

, _left(NULL)

, _right(NULL)

{}

};

template

class HuffmanTree//huffman樹的實現(xiàn)

{

typedef HuffmanNode Node;

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 minHeap(array, size);

Heap minHeap;

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 q;

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;

tree.CreateHuffmanTree(ar, sizeof(ar) / sizeof(ar[0]), -1);

tree.LevelOrder();

}