Question

数据结构 简答题 求助

Answer 1

八个权值是 6 7 19 2 11 25 4 32

(1) 从小到大排序 2 4 6 7 11 19 25 32 (这是有序序列)
(2) 每次提取最小的两个结点,取结点2和结点4,组成新结点N6,其权值=2+4=6,
    取数值较小的结点作为左分支,结点2作为左分支,而结点4就作为右分支.
(3) 将新结点N6放入有序序列,保持从小到大排序:
    6 N6 7 11 19 25 32
(4) 重复步骤(2),提取最小的两个结点,结点6与N6组成新结点N12,其权值=6+6=12,
    结点6与N6权值相同,但N6是新结点,将结点6作为左分支,新结点N6就作为右分支.
(5) 将新结点N12放入有序序列,保持从小到大排序:
    7 11 N12 19 25 32
(6) 重复步骤(2),提取最小的两个结点,结点7与结点11组成新结点N18,其权值=7+11=18,
    结点7的数值较小,作为左分支,结点11就作为右分支.
(7) 将新结点N18放入有序序列,保持从小到大排序:
    N12 N18 19 25 32
(8) 重复步骤(2),提取最小的两个结点,N12与N18组成新结点N30,其权值=12+18=30,
    N12的数值较小,作为左分支,N18就作为右分支.
(9) 将新结点N30放入有序序列,保持从小到大排序:
    19 25 N30 32
(10)重复步骤(2),提取最小的两个结点,结点19与结点25组成新结点N44,其权值=19+25=44,
    结点19的数值较小,作为左分支,结点25就作为右分支.
(11)将新结点N44放入有序序列,保持从小到大排序:
    N30 32 N44
(12)重复步骤(2),提取最小的两个结点,N30与结点32组成新结点N62,其权值=30+32=62,
    N30的数值较小,作为左分支,结点32就作为右分支.
(13)将新结点N62放入有序序列,保持从小到大排序:
    N44 N62
(14)重复步骤(2),提取剩下的两个结点,N44与N62组成新结点N106,其权值=44+62=106,
    数值较小的N44作为左分支,N62就作为右分支.
    有序序列已经没有结点,最后得到"哈夫曼树":

           N106
      /           \
     N44          N62
    /  \       /       \
   19  25     N30      32
           /       \
          N12      N18
         /  \     /  \
        6   N6   7   11
           /  \ 
          2    4

带权路径长度(WPL):
根结点N106到结点32的路径长度是2,结点32的带权路径长度是32*2
根结点N106到结点25的路径长度是2,结点25的带权路径长度是25*2
根结点N106到结点19的路径长度是2,结点19的带权路径长度是19*2
根结点N106到结点11的路径长度是4,结点11的带权路径长度是11*4
根结点N106到结点7的路径长度是4,结点7的带权路径长度是7*4
根结点N106到结点6的路径长度是4,结点6的带权路径长度是6*4
根结点N106到结点4的路径长度是5,结点4的带权路径长度是4*5
根结点N106到结点2的路径长度是5,结点2的带权路径长度是2*5
所以,哈夫曼树的带权路径长度(WPL)等于
32*2 + 25*2 + 19*2 + 11*4 + 7*4 + 6*4 + 4*5 + 2*5 = 278

哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N106到结点32,经历两次右分支,结点32的编码就是11
从根结点N106到结点25,先经历左分支,然后是右分支,结点25的编码就是01
从根结点N106到结点19,经历两次左分支,结点19的编码就是00
从根结点N106到结点11,经历了右分支,左分支,最后是两次右分支,结点11的编码就是1011
从根结点N106到结点7,经历了右分支,左分支,右分支,左分支,结点7的编码就是1010
从根结点N106到结点6,先经历右分支,然后是三次左分支,结点6的编码就是1000
从根结点N106到结点4,经历了右分支,两次左分支,两次右分支,结点4的编码就是10011
从根结点N106到结点2,经历了右分支,两次左分支,然后是右分支,左分支,结点2的编码就是10010
得出所有结点的"哈夫曼编码":
权值32: 11
权值25: 01
权值19: 00
权值11: 1011
权值7 : 1010
权值6 : 1000
权值4 : 10011
权值2 : 10010


//C语言测试程序(来自其他网友)
//
//输入构造哈夫曼树中带权叶子结点数(n)：8
//输入8个整数作为权值：6 7 19 2 11 25 4 32
//可以得出哈夫曼树的广义表形式,带权路径长度,以及哈夫曼编码.

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
struct BTreeNode
{
    ElemType data;
    struct BTreeNode* left;
    struct BTreeNode* right;
};

//1、输出二叉树，可在前序遍历的基础上修改。
//   采用广义表格式，元素类型为int
void PrintBTree_int(struct BTreeNode* BT)
{
    if (BT != NULL)
    {
        printf("%d", BT->data); //输出根结点的值
        if (BT->left != NULL || BT->right != NULL)
        {
            printf("(");
            PrintBTree_int(BT->left); //输出左子树
            if (BT->right != NULL)
                printf(",");
            PrintBTree_int(BT->right); //输出右子树
            printf(")");
        }
    }
}

//2、根据数组 a 中 n 个权值建立一棵哈夫曼树，返回树根指针
struct BTreeNode* CreateHuffman(ElemType a[], int n)
{
    int i, j;
    struct BTreeNode **b, *q;
    b = malloc(n*sizeof(struct BTreeNode));
    //初始化b指针数组，使每个指针元素指向a数组中对应的元素结点
    for (i = 0; i < n; i++)
    {
        b[i] = malloc(sizeof(struct BTreeNode));
        b[i]->data = a[i];
        b[i]->left = b[i]->right = NULL;
    }
    for (i = 1; i < n; i++)//进行 n-1 次循环建立哈夫曼树
    {
        //k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标
        int k1 = -1, k2;
        //让k1初始指向森林中第一棵树，k2指向第二棵
        for (j = 0; j < n; j++)
        {
            if (b[j] != NULL && k1 == -1)
            {
                k1 = j;
                continue;
            }
            if (b[j] != NULL)
            {
                k2 = j;
                break;
            }
        }
        //从当前森林中求出最小权值树和次最小
        for (j = k2; j < n; j++)
        {
            if (b[j] != NULL)
            {
                if (b[j]->data < b[k1]->data)
                {
                    k2 = k1;
                    k1 = j;
                }
                else if (b[j]->data < b[k2]->data)
                    k2 = j;
            }
        }
        //由最小权值树和次最小权值树建立一棵新树，q指向树根结点
        q = malloc(sizeof(struct BTreeNode));
        q->data = b[k1]->data + b[k2]->data;
        q->left = b[k1];
        q->right = b[k2];

        b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置
        b[k2] = NULL;//k2位置为空
    }
    free(b); //删除动态建立的数组b
    return q; //返回整个哈夫曼树的树根指针
}

//3、求哈夫曼树的带权路径长度
ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始为0
{
    if (FBT == NULL) //空树返回0
        return 0;
    else
    {
     if (FBT->left == NULL && FBT->right == NULL)//访问到叶子结点
     {
            printf("+ %d * %d ",FBT->data,len);
            return FBT->data * len;
     }
     else //访问到非叶子结点，进行递归调用，
     {    //返回左右子树的带权路径长度之和，len递增
     return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
     }
    }
}

//4、哈夫曼编码（可以根据哈夫曼树带权路径长度的算法基础上进行修改）
void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值为0
{
    //定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一
    static int a[10];
    int i;
    //访问到叶子结点时输出其保存在数组a中的0和1序列编码
    if (FBT != NULL)
    {
        if (FBT->left == NULL && FBT->right == NULL)
        {
            printf("权值为%d的编码：", FBT->data);
            for (i = 0; i < len; i++)
                printf("%d", a[i]);
            printf("\n");
        }
        else //访问到非叶子结点时分别向左右子树递归调用，
        {    //并把分支上的0、1编码保存到数组a的对应元素中，
             //向下深入一层时len值增1
            a[len] = 0;
            HuffManCoding(FBT->left, len + 1);
            a[len] = 1;
            HuffManCoding(FBT->right, len + 1);
        }
    }
}

int main()
{
    int n, i;
    ElemType* a;
    struct BTreeNode* fbt;
    printf("输入构造哈夫曼树中带权叶子结点数(n)：");
    while(1)
    {
        scanf("%d", &n);
        if (n > 1)
            break;
        else
            printf("重输n值：");
    }
    a = malloc(n*sizeof(ElemType));
    printf("输入%d个整数作为权值：", n);
    for (i = 0; i < n; i++)
        scanf(" %d", &a[i]);
    fbt = CreateHuffman(a, n);
    printf("广义表形式的哈夫曼树：");
    PrintBTree_int(fbt);
    printf("\n");
    printf("哈夫曼树的带权路径长度：\n");
    printf("=");
    printf("\n=%d\n", WeightPathLength(fbt, 0));
    printf("树中每个叶子结点的哈夫曼编码：\n");
    HuffManCoding(fbt, 0);

    return 0;
}