当前位置：首页 > article >正文

数据结构_赫夫曼树（基于例题）

article 2024/12/22 20:32:41

赫夫曼树的构建与编码

哈夫曼树类

属性有权值，父母值，左孩子值和右孩子值，实现的方法有构造哈夫曼树和哈夫曼编码

class HuNode
{
public:
    int weight, parent, lch, rch;
    void create_Tree(HuNode* HT, int n);
    void create_Code(HuNode* HT, char** code, int n);
};

在构造哈夫曼树的方法中，参数是需要构造的树根和节点个数；如果结点数小于等于1，直接返回；计算哈夫曼数组中共有的元素，然后将这些元素的左右孩子的值和父母值全部初始化为0，再输入权值，构造哈夫曼树的方法是，在现有的哈夫曼数组中选择两个双亲域为0，且权值最小的节点，返回他们在HT中的序号，并且他们的双亲域都为i值，表示这两个结点已在树中，下次再选择两个较小的结点时不会再选中，s1 s2分别作为i的左右孩子，i的权值为左右孩子权值之和，至此结束完毕

void HuNode::create_Tree(HuNode* HT, int n)
{
    if (n <= 1)
    {
        return;
    }

    int i, m, s1, s2;
    m = 2 * n - 1; // 哈夫曼数组中共有的元素

    for (i = 1; i <= m; i++)
    {
        HT[i].lch = 0;
        HT[i].rch = 0;
        HT[i].parent = 0;
    }
    for (i = 1; i <= n; i++)
    {
        cin >> HT[i].weight;
    }

    // 创建哈夫曼树
    for (i = n + 1; i <= m; i++)
    {
        s1 = -1;
        s2 = -1;
        Selete(HT, i - 1, s1, s2);
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lch = s1;
        HT[i].rch = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

在构造编码的函数中，首先构造一个临时数组存放编码，和编码长度计数器，利用循环逐个字符求哈夫曼编码，当当前结点的双亲域不等于0时，如果他的左孩子结点等于当前结点的值，则此节点就是左孩子结点，所以此时左子节点编码为0，计数器加1，否则，为右子节点，编码为1，计数器加1，当前结点的值赋值为父节点的值，父结点的值赋值为当前结点的父节点的值，找完编码后，由于是从下面开始往上照，所以编码是反着的，所以输出时要反着输出

void HuNode::create_Code(HuNode* HT, int n)
{
    int i, current, parent, k, j;
    char temp[100]; // 临时数组存放编码

    for (i = 1; i <= n; i++)
    {
        current = i;
        parent = HT[i].parent;
        k = 0; // 编码长度计数器

        while (parent != 0)
        {
            if (HT[parent].lch == current)
            {
                temp[k] = '0'; // 左子节点编码为 '0'
                k++;
            }
            else
            {
                temp[k] = '1';
                k++;
            }
            current = parent;
            parent = HT[current].parent;
        }
        temp[k] = '\0';

        cout << HT[i].weight << "-";
        for (j = k - 1; j >= 0; j--)
        {
            cout << temp[j];
        }
        cout << endl;
    }
}

选择两个较小值结点函数

void Selete(HuNode* HT, int n, int& s1, int& s2)
{
    for (int i = 1; i <= n; i++)
    {
        if (HT[i].parent == 0) // 仅考虑未被合并的节点
        {
            if (s1 == -1 || HT[i].weight < HT[s1].weight)
            {
                s1 = i; // 最小值
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (HT[i].parent == 0 && i != s1)
        {
            if (s1 == -1 || HT[i].weight < HT[s2].weight)
            {
                s2 = i;
            }
        }
    }
}

主函数

int main()
{
    int t, n;
    cin >> t;

    while (t--)
    {
        cin >> n; // 有n个权值
        HuNode* HT = new HuNode[2 * n];
        HT->create_Tree(HT, n);
        HT->create_Code(HT, n);
    }

    return 0;
}

赫夫曼树解码

解码函数，依次读入二进制码，读入0，则走向左孩子，读入1，则走向右孩子，一旦到达某叶子节点，即可译出字符，然后再从根结点出发继续译码，直到结束

int HuNode::Decode(const string codestr, char txtstr[], int n)
{
    int index, root, i, curNode;
    index = 0;
    root = 2 * n - 1; // 根节点编号
    curNode = root;

    for (i = 0; i < codestr.length(); i++)
    {
        if (codestr[i] == '0')
        {
            curNode = this[curNode].lch;
        }
        else
        {
            curNode = this[curNode].rch;
        }

        // 解码失败
        if (curNode == 0)
        {
            return error;
        }
        // 是叶子节点
        if (this[curNode].lch == 0 && this[curNode].rch == 0)
        {
            txtstr[index] = this[curNode].data;
            index++;
            curNode = root;
        }
    }

    if (curNode != root)
    {
        return error;
    }
    txtstr[index] = '\0';
    return ok;
}