哈夫曼树与编码译码实现(2)

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

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);   
    }
}