数据结构（十）

学习数据结构与算法过程中的心得体会以及知识点的整理，方便我自己查找，也希望可以和大家一起交流。

—— Huffman编码树 ——

1.题目描述

构造一个具有n个外部节点的扩充二叉树，每个外部节点Ki有一个Wi对应，作为该外部节点的权。使得这个扩充二叉树的叶节点带权外部路径长度总和最小：

        Min( W1 * L1 + W2 * L2 + W3 * L3 + … + Wn * Ln)

Wi:每个节点的权值。
Li:根节点到第i个外部叶子节点的距离。
编程计算最小外部路径长度总和。

1.1输入

第一行输入一个整数t，代表测试数据的组数。
对于每组测试数据，第一行输入一个整数n，外部节点的个数。第二行输入n个整数，代表各个外部节点的权值。 2<=N<=100

1.2输出

输出最小外部路径长度总和。

1.3样例输入与输出

样例输入
2
3
1 2 3
4
1 1 3 5
样例输出
9
17

2.代码实现

c

#include<stdio.h>

void sort(int weight[],int group)
{
    int t;
    for(int i=0;i<group;i++)
    {
        for(int j=0;j<group-i-1;j++)
        {
            if(weight[j]<weight[j+1])
            {
                t=weight[j];
                weight[j]=weight[j+1];
                weight[j+1]=t;
            }
        }
    }
}

int count(int weight[],int group)
{
    if(group==1)
        return 0;
    else
    {
        sort(weight,group);
        weight[group-2]=weight[group-1]+weight[group-2];
        return weight[group-2]+count(weight,group-1);
    }
}

int main()
{
    int num,group;
    scanf("%d",&num);
    while(num--)
    {
        int i;
        scanf("%d",&group);
        int weight[group];
        for(i=0;i<group;i++)
        {
            scanf("%d",&weight[i]);
        }
        printf("%d\n",count(weight,group));
    }
    return 0;
}

c++

#include <iostream>
#include <queue>

using namespace std;

void num_sort(int weight[],int group)
{
    int t;
    for(int i=0;i<group;i++)
    {
        for(int j=0;j<group-i-1;j++)
        {
            if(weight[j]<weight[j+1])
            {
                t=weight[j];
                weight[j]=weight[j+1];
                weight[j+1]=t;
            }
        }
    }
}

int num_count(int weight[],int group)
{
    if(group==1)
        return 0;
    else
    {
        num_sort(weight,group);
        weight[group-2]=weight[group-1]+weight[group-2];
        return weight[group-2]+num_count(weight,group-1);
    }
}

int main()
{
    int num,group;
    cin >>num;
    while(num--)
    {
        int i;
        cin >>group;
        int weight[group];
        for(i=0;i<group;i++)
        {
            cin >>weight[i];
        }
        cout <<num_count(weight,group) <<endl;
    }
    return 0;
}

3.代码说明

其实核心算法不是很难，只要学过二叉树，不用学堆结构都可以实现，无非是排序+计算权重。c和c++差不大，就是基本语法改了一点点。
要了解Huffman编码树的可以点击教程查看。