二叉树_哈夫曼树带权路径长度_c哈夫曼树(2)

struct TNode() : weight(0), parent(0), lchild(0), rchild(0){}

};

class HuffTree

{

public:

void HuffmanCode(vector<TNode> &HT, vector<string> &HC, const vector<int> &wgh);

void HuffDecodeing(vector<TNode> &HT, vector<string> &HC, vector<int> &SrcCode);

private:

void InitHuffTree(vector<TNode> &HT, const vector<int> &wgh);

void BuildHuffTree(vector<TNode> &HT, const vector<int> &wgh);

void SelectTwoMin(vector<TNode> &HT, int n, int &min1, int &min2);

void HuffCodeing(vector<TNode> &HT, vector<string> &HC, const vector<int> &wgh);

};

void HuffTree::InitHuffTree(vector<TNode> &HT, const vector<int> &wgh)

{

if (wgh.empty())

{

return;

}

int wghSize = wgh.size();

int m = 2 * wghSize - 1;

HT.resize(m + 1);

for (int i = 1; i <= wghSize; ++i)

{

HT[i].weight = wgh[i - 1];

}

}

void HuffTree::SelectTwoMin(vector<TNode> &HT, int n, int &min1, int &min2)

{

if (HT.empty())

{

return;

}

multimap<int, int> wghMap;

multimap<int, int>::iterator iter;

for (int i = 1; i < n; ++i)

{

if (HT[i].parent == 0)

{

wghMap.insert(make_pair(HT[i].weight, i));

}

}

if (wghMap.size() >= 2)

{

iter = wghMap.begin();

min1 = iter->second;

min2 = (++iter)->second;

}

}

void HuffTree::BuildHuffTree(vector<TNode> &HT, const vector<int> &wgh)

{

if (HT.empty() || wgh.empty())

{

return;

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-33550-2.html