本文共 927 字，大约阅读时间需要 3 分钟。

数据结构（十）

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

—— 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
   
    void sort(int weight[],int group){
       int t;    for(int i=0;i
   

c++

#include 
   
    #include 
    
     using namespace std;void num_sort(int weight[],int group){
       int t;    for(int i=0;i
     
      >num;    while(num--)    {
           int i;        cin >>group;        int weight[group];        for(i=0;i
      
       >weight[i];        }        cout <
       
        <
       
      
     
    
   

3.代码说明

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

转载地址：http://efazi.baihongyu.com/