哈夫曼树wpl_哈夫曼树的带权路径长度是( )_哈夫曼树怎么画

哈夫曼树也叫做最优二叉树。。如果扩充二叉树的外部节点都带有一定的权，可将外部路径长度这一概念加以推广。设扩充二叉树具有m个带权的外部节点，那么从根节点到各个外部节点的路径长度与相应结点权的乘积的和，叫做扩充二叉树的带权的外部路径长度。。记作WPL。。。(摘抄自算法与数据结构课本)。哈夫曼树的带权路径长度是( )

而关于哈夫曼树的应用，有哈夫曼编码与二路归并排序。。哈夫曼编码就是比如说要用二进制编译一段文字编码。。所以就需要把出现频率比较高的字符的编码放在靠近根结点的位置，这样的话，想要找到该字符的编码就能够节省相当一部分篇幅了。。哈夫曼树的带权路径长度是( )。而二路归并排序就是说有n个已经排序的文件，每个文件包含的记录个数都已知可以采用两两合并的方法，把所有的文件的记录合到一个大文件中去，使得这个文件中的记录全部排序。。

说了这么多，，有没有赶脚到挺迷惑的啊。哈哈，直接上代码吧。。。

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <stack>
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a));
#define For(a,b) for(int i = a;i<b;i++)
#define LL long long
#define MAX_N 100010
using namespace std;
struct HfNode
{
    int oval;
    int lchil;
    int rchil;
    int par;
};
struct HfTree
{
    int m;
    int root;
    struct HfNode * ht;
};
typedef struct HfTree * PHtTree;
PHtTree Pht;
PHtTree huffman(int num,int *w)
{
    /*
        申请指向哈夫曼数的指针
    */
    Pht = (PHtTree)malloc(sizeof(HfNode));
    if(Pht == nullptr)
    {
        cout<<"Out of space"<<endl;
        return Pht;
    }
    /*

        申请对于该哈夫曼树的一个空间是 ——  2*num-1 ——
        的顺序线性表空间

    */
    Pht->ht = (HfNode *)malloc(sizeof(HfNode) * (2 * num - 1));
    if(Pht->ht == nullptr)
    {
        cout<<"Out of space"<<endl;
        return Pht;
    }
    /*

        该for循环是给顺序线性表中的各元素初始化或者说叫作标记
    */
    for(int i = 0; i<2*num-1; i++)
    {
        Pht->ht[i].lchil = -1;
        Pht->ht[i].rchil = -1;
        Pht->ht[i].par = -1;
        if(i<num) Pht->ht[i].oval = w[i];
        else Pht->ht[i].oval = -1;
    }
    /*

        该for循环是将一个最佳的哈夫曼树在顺序链表中存储

    */
    for(int i = 0; i<num-1; i++)
    {
        int m1 = INF,m2 = INF;
        int x1 = -1,x2 = -1;
        for(int j = 0; j<num + i; j++)
        {
            if(Pht->ht[j].oval < m1 && Pht->ht[j].par == -1)
            {
                m2 = m1;
                x2 = x1;
                x1 = j;
                m1 = Pht->ht[j].oval;
            }
            else if(Pht->ht[j].oval < m2 && Pht->ht[j].par == -1)
            {
                m2 = Pht->ht[j].oval;
                x2 = j;
            }
        }
        Pht->ht[x1].par = num + i;
        Pht->ht[x2].par = num + i;
        Pht->ht[num + i].oval = m1 + m2;
        Pht->ht[num + i].lchil = x1;
        Pht->ht[num + i].rchil = x2;
    }
    Pht->root = 2*num-2;
    return Pht;
}
int main()
{
    Pht = nullptr;
    int w[4] = {9,6,3,2};
    huffman(4,w);
    int WPL = 0,WPL2 = 0;
    /*

        从外部结点入手，计算带权最短外部路径长度

    */
    for(int i = 0; i<4; i++)
    {
        int ways = 0;
        int parent = 0;
        int cur = i;
        /*

            该while循环是为了找到此外部节点到根结点的路径距离

        */
        while(parent != -1)
        {
            ways++;
            parent = Pht->ht[cur].par;
            cur = parent;
        }
        ways--;
        WPL += (Pht->ht[i].oval*ways);
    }
    cout<<"第一种扩充二叉树的带权的最短外部路径长度："<<WPL<<endl<<endl;
    /*

        从内部结点入手，计算带权最短外部路径长度

    */
    for(int i = 0; i<2*4-1; i++)
    {
        /*

            判断是否是扩充二叉树的内部节点。是则加，否则不处理。。
            而且，如果把i的初始值改为4，则不需要判断，可直接加。。

        */
        if(Pht->ht[i].lchil != -1 && Pht->ht[i].rchil != -1)
        {
            WPL2 += Pht->ht[i].oval;
        }
    }
    cout<<"第二种扩充二叉树的带权的最短外部路径长度："<<WPL2<<endl<<endl;
    return 0;
}

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