huffmanNode.h
#ifndef __HUFFMANNODE_H__ #define __HUFFMANNODE_H__ class huffmanNode { public: int weight; int lchild, rchild, parent; }; #endif
huffmanTree.cpp
#include <iostream> #include "huffmanNode.h" using namespace std; void selectMinWeight(huffmanNode *_huffmanTree, int _num, int &_minIndex1, int &_minIndex2) { int i = 0, minWeight = 0; for (i = 0; i < _num; i++) if (_huffmanTree[i].parent == -1) { minWeight = i; break; } for (i = 0; i < _num; i++) if (_huffmanTree[i].parent == -1) if (_huffmanTree[i].weight < _huffmanTree[minWeight].weight) minWeight = i; _minIndex1 = minWeight; for (i = 0; i < _num; i++) if (_huffmanTree[i].parent == -1 && i != _minIndex1) { minWeight = i; break; } for (i = 0; i < _num; i++) if (_huffmanTree[i].parent == -1 && i != _minIndex1) if (_huffmanTree[i].weight < _huffmanTree[minWeight].weight) minWeight = i; _minIndex2 = minWeight; } //构造哈夫曼树 void HuffmanTree(huffmanNode *_huffmanTree, int _weight[], int _num) { int i = 0; int minIndex1 = -1, minIndex2 = -1; for (i = 0; i < 2 * _num - 1; i++) { _huffmanTree[i].parent = -1; _huffmanTree[i].lchild = -1; _huffmanTree[i].rchild = -1; } for (i = 0; i < _num; i++) _huffmanTree[i].weight = _weight[i]; //合并节点，构建哈夫曼树 for (i = _num; i < 2 * _num - 1; i++) { selectMinWeight(_huffmanTree, i, minIndex1, minIndex2); _huffmanTree[minIndex1].parent = i; _huffmanTree[minIndex2].parent = i; _huffmanTree[i].lchild = minIndex1; _huffmanTree[i].rchild = minIndex2; _huffmanTree[i].weight = _huffmanTree[minIndex1].weight + _huffmanTree[minIndex2].weight; cout << _huffmanTree[i].weight << "(" << _huffmanTree[minIndex1].weight << "," << _huffmanTree[minIndex2].weight << ")" << endl; } } //求哈夫曼树的哈夫曼编码 void HuffmanCode(huffmanNode *_huffmanTree, int _num) { int parentIndex = -1, j = 0; vector<int> code; vector<int> nodeCode; for (int i = 0; i < _num; i++) { j = i; while(_huffmanTree[j].parent != -1) { parentIndex = _huffmanTree[j].parent; if (j == _huffmanTree[parentIndex].lchild) nodeCode.insert(nodeCode.begin(), 0); else nodeCode.insert(nodeCode.begin(), 1); j = parentIndex; } code.insert(code.end(), nodeCode.begin(), nodeCode.end()); nodeCode.clear(); } for (unsigned int i = 0; i < code.size(); i++) cout << code.at(i); cout << endl; } int main() { huffmanNode huffmanTree[2 * 5 - 1]; int weight[] = { 35, 25, 15, 15, 10 }; HuffmanTree(huffmanTree, weight, sizeof(weight) / sizeof(4)); HuffmanCode(huffmanTree, sizeof(weight) / sizeof(4)); return 0; }
输出
5(2,3) 9(4,5) 14(5,9)
即：
坐标： 0 1 2 3 4 5 6 7 8 9
权重：(2)(4)(5)(3)(-1)(-1)(-1)(-1)(-1)(-1)
|| || \/ 4(5) / \ 0(2) 3(3) || || \/ 4(5) 5(9) / \ / \ 0(2) 3(3) 1(4) 2(5) || || \/ 6(14) / \ 4(5) 5(9) / \ / \ 0(2) 3(3) 1(4) 2(5) _________________________________________ 110110100100
