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

}

int htSize = HT.size();

int wghSize = wgh.size();

int wghs1, wghs2;

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

{

SelectTwoMin(HT, i, wghs1, wghs2);

HT[wghs1].parent = i;

HT[wghs2].parent = i;

HT[i].lchild = wghs1;

HT[i].rchild = wghs2;

HT[i].weight = HT[wghs1].weight + HT[wghs2].weight;

}

}

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

{

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

{

return;

}

int n = wgh.size() + 1;

int cha, par;

string codeTmp, code;

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

{

code.clear();

codeTmp.clear();

for (cha = i, par = HT[i].parent; par != 0; cha = par, par = HT[par].parent)

{

if (HT[par].lchild == cha)

{

codeTmp = codeTmp + "0";

}

else

{

codeTmp = codeTmp + "1";

}

}

for (int j = codeTmp.size() - 1; j >= 0; --j)

{

code = code + codeTmp[j];

}

HC.push_back(code);

}

}

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

{

if (HT.empty() || HC.empty())

{

return;

}

string codeTmp;

int p, strLen;

for (int i = 0; i < HC.size(); ++i)

{

p = HT.size() - 1; //回到根结点

codeTmp = HC[i];

strLen = codeTmp.size();

for (int j = 0; j < strLen; ++j)

{

if (codeTmp[j] == '0')

{

p = HT[p].lchild;

}

else

{

p = HT[p].rchild;

}

}

SrcCode.push_back(HT[p].weight);

}

}

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

{

if (wgh.empty())

{

return;

}

InitHuffTree(HT, wgh);

BuildHuffTree(HT, wgh);

HuffCodeing(HT, HC, wgh);

}

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