题目30：哈夫曼树-白红宇

题目30：哈夫曼树

阅读量：5204 次

发布时间：2019-06-13

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

http://ac.jobdu.com/problem.php?cid=1040&pid=29

题目描述：

哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。

输入：

输入有多组数据。

每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

输出：

输出权值。

样例输入：

5  1 2 2 5 9

样例输出：

// 题目30：哈夫曼树.cpp: 主项目文件。//不使用优先队列（堆结构）#include "stdafx.h"#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               using namespace std;const int MAX=1<<30;const int N=20003;int a[N];//int level[N];bool used[N];int n;int selectMin(int length){ int minIndex=-1,min=MAX; for(int i=0;i
               
                >n&&n!=0) { for(int i=0;i
                
                 >a[i]; int wholeWeight=huffmanTree(); cout<
                 
                  <