首页 > 试题广场 > 哈夫曼树
[编程题]哈夫曼树
哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。

输入描述:
输入有多组数据。
每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过100,2<=n<=1000)。


输出描述:
输出权值。
示例1

输入

5  
1 2 2 5 9

输出

37

68个回答

添加回答
解题关键是权值的求法:赫夫曼树的带权路径之和为各叶子节点的权值与路径长度(层次数减一或从根节点到达叶子节点路径上的非叶子节点的个数)之积的和。在构造赫夫曼树时,非叶子节点也会带有权值(为其子节点的权值之和),当加上一个非叶子节点的权值时相当于加上以其为根节点的子树的所有叶子节点的权值。而加上从根节点到叶子节点路径上的非叶子节点权值,就包含了该叶子节点的带权路径长度。所以带权路径之和即为所有非叶子节点的权值之和。
接下来就是按照构造赫夫曼树的方法求出各非叶子节点的权值。
关键在于选取节点中最小的两个节点,并删除这两节点并添加新的节点。
最笨的方法是添加辅助数组来记录集合中的节点,并通过两次选择选取最小的节点。
第二种容易想到的方法自然是建立小顶堆,假设元素数为n,堆顶元素即为最小值,可通过将最后的节点提到堆顶,然后进行调整算法建立元素数为n-1的小顶堆,将堆顶元素与第一次选取的值相加便得到了新的节点的权值,与sum相加后,再次调整为小顶堆。重复操作直至元素数为1。
发表于 2018-03-07 11:14:16 回复(0)
#include<iostream>
#include<queue>
using namespace std;
int main(){
    int n,temp,a,b;
    int weight;
    priority_queue<int,vector<int>,greater<int>> minheap;
    while(cin>>n)
    {
        weight = 0;
        for(int i= 0;i < n;i++)
        {
            cin>>temp;
            minheap.push(temp);
        }
        while(minheap.size()!= 1)
        {
            a = minheap.top();
            minheap.pop();
            b = minheap.top();
            minheap.pop();
            weight = weight + a +b;
            minheap.push(a+b);
             
        }
        cout<<weight<<endl;
        minheap.pop();
    }    
    return 0;
}


发表于 2016-08-19 08:39:53 回复(1)
import java.util.Scanner;
import java.util.PriorityQueue;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            PriorityQueue<Integer> q = new PriorityQueue<Integer>();
            for(int i=0;i<n;i++)
                q.add(in.nextInt());
            int ans = 0;
            while(q.size()>1){
                int first = q.poll();
                int sec = q.poll();
                ans += (first + sec);
                q.add(first+sec);
            }
            System.out.println(ans);
        }
    }
}

发表于 2018-02-27 14:39:26 回复(0)
#include <queue>
#include <stdio.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> Q; //用优先队列实现最小堆
int main(){
    int n;
    while(scanf("%d",&n)!=EOF)
    {
            while(!Q.empty())Q.pop();
            for(int i=0;i<n;++i)
            {
                int x;
                scanf("%d",&x);
                Q.push(x);
            }
            int ans=0;
            while(Q.size()>1){
                int a=Q.top();
                Q.pop();
                int b=Q.top();
                Q.pop();
                ans+=a+b;
                Q.push(a+b);
            }
            printf("%d\n",ans);
     }
    return 0;
}
发表于 2018-01-14 21:06:31 回复(0)
#include<iostream>
#include<limits.h>
using namespace std;
typedef struct HuffmanNode{
    long int weight;
    int parent;
    int lchild;
    int rchild;
}HuffmanNode,*HuffmanTree;
void select(int& s1,int& s2,HuffmanTree T, int n);
int main()
{
    int n;
    HuffmanTree Tree;
    while(cin>>n)
        {
        int m=2*n-1;
     Tree=(HuffmanTree)malloc(sizeof(HuffmanNode)*(m+1));
  int i;
  for(i=1;i<=n;i++)
  {
   int weight;
         cin>>weight;
   Tree[i].weight=weight;
   Tree[i].parent=0;
   Tree[i].lchild=0;
   Tree[i].rchild=0;
  } 
  for(;i<=m;i++)
  {
   Tree[i].weight=0;
   Tree[i].lchild=0;
   Tree[i].rchild=0;
   Tree[i].parent=0;
  }
  for(i=n+1;i<=m;i++)
  {
   int s1,s2;
   select(s1,s2,Tree,i-1);
   Tree[i].lchild=s1;
   Tree[i].rchild=s2;
   Tree[s1].parent=i;
   Tree[s2].parent=i;
   Tree[i].weight=Tree[s1].weight+Tree[s2].weight;
  }
  long int sum=0;
  for(i=1;i<=n;i++)
  {
   int p,f,j=0;
   for(p=i,f=Tree[p].parent;f!=0;p=f,f=Tree[p].parent)
   {
    j++;
   }
   sum=sum+(Tree[i].weight*j);
  }
  cout<<sum<<endl;
     free(Tree);
    }
    
   return 0;  
}
void select(int& s1,int& s2,HuffmanTree T,int n)
{
 int i;
 long int min=LONG_MAX,secMin=LONG_MAX;
 for(i=1;i<=n;i++)
 {
  if(T[i].parent==0)
  {
   if(T[i].weight<=min)
   {
    s2=s1;
    secMin=min;
    s1=i;
    min=T[i].weight;    
   }
   else if(T[i].weight<=secMin)   
   {
    s2=i;
    secMin=T[i].weight;
   }
  }
 }
}
 

发表于 2017-03-20 17:04:32 回复(0)
#include<stdlib.h>  //储存malloc的文件
#include <stdio.h>

void sort(int *array, int begin, int num);
int main(){
int num;
int height = 0;
int *array = NULL;
while (scanf("%d", &num) != EOF){

//创建动态数组;注意使用之后要释放内存
array = (int *)malloc(num * sizeof(int));

for (int k = 0; k < num; k++){
scanf("%d", &array[k]);
}
sort(array, 0, num);

int i = 1, sum = 0;
while (i<num)
{
sort(array, i - 1, num);//每次都要重新排序,因为生成了新的节点  
sum += array[i] + array[i - 1];//计算父亲   
array[i] = array[i] + array[i - 1];//将小树生成新的节点  
i++;
}
printf("%d\n", sum);

}
//释放内存
free(array);
return 0;
}
//传地址进行排序
void sort(int *array, int begin, int num){
//现将数组进行排序;从小到大,冒泡虽然慢,但是比较容易实现
for (int i = begin; i < num; i++){
for (int j = i + 1; j < num; j++){
if (array[j] < array[i]){
int tmp = array[j];
array[j] = array[i];
array[i] = tmp;
}
}
}
}
发表于 2016-08-23 10:16:41 回复(0)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    int n, sum, temp;
    vector<int> s;
    while(cin >> n)
    {
        sum = 0;
        for(int i = 0; i!= n; ++i)
        {
            cin >> temp;
            s.push_back(temp);
        }
        int bg = 0, ed = n;
        while(ed-bg != 1)
        {
            sort(&s[bg], &s[ed]);
            temp = s[bg++] + s[bg++];
            sum += temp;
            s.push_back(temp);
            ed++;
        }
        cout << sum << endl;
        s.clear();
    }
}

发表于 2018-01-13 13:57:11 回复(0)
#include <iostream>
#include <queue>
using namespace std;
int main()
{
    int n,ans,i;
    priority_queue<int, vector<int>, greater<int>> tmp;
    cin>>n;
    for(i=0;i<n;++i)
    {
        cin>>ans;
        tmp.push(ans);
    }
    int sum=0;
    while(tmp.size()>1)
    {
        int min1,min2;
        min1=tmp.top();
        tmp.pop();
        min2=tmp.top();
        tmp.pop();
        sum+=min1+min2;
        tmp.push(min1+min2);
    }
    cout<<sum<<endl;
    return 0;
}
发表于 2019-04-28 10:40:51 回复(0)
 #include<iostream>
#include<queue>


using namespace std;

int main()
{
    //输入多少个数据 
    int n;
    cin>>n;
    //优先队列
    //vector:盛放队列中的数据的容器 
    //greater:队列中的数据从小到大 
    priority_queue<int, vector<int>, greater<int> > q; 
    //要输入的结点数据
    int nodeData; 
    for(int i=0; i<n; i++) 
    {
        cin>>nodeData;
        //把数据放到队列中并自动从小到大排列 
        q.push(nodeData);
    }
    
    //计算哈夫曼值,a,b分别为每次取出的头两个结点(最小的两个) 
    int sum=0; 
    int a, b;
    while(q.size()>1)
    {
        a=q.top();
        q.pop();
        b=q.top();
        q.pop();
        q.push(a+b);
        sum=sum+a+b; 
    }
    cout<<sum<<endl;
    
    return 0; 
}
发表于 2019-02-23 20:52:12 回复(0)
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef struct HuffmanTree{
    int data;
    int weight;
    HuffmanTree *lchild,*rchild;
} HT;
int n;
vector<HT> seq;
bool cmp(HT a,HT b){
    return a.data<b.data;
}
void insert_node(HT* node){
    if(seq.empty()){
        seq.push_back(*node);
        return;
    }
    vector<HT>::iterator it = seq.begin();
    for(it;it != seq.end();it++){
        if(node->data <= it->data){
            seq.insert(it,*node);
            return;
        }
    }
    seq.push_back(*node);
}
HT* buildHT(){
    while(1){
        HT *fnode = (HT*) malloc(sizeof(HT));
        HT *node_l = (HT*) malloc(sizeof(HT));
        HT *node_r = (HT*) malloc(sizeof(HT));
        *node_l = seq[0];
        *node_r = seq[1];
        fnode->data = node_l->data + node_r->data;
        fnode->lchild = node_l;
        fnode->rchild = node_r;
        seq.erase(seq.begin());
        seq.erase(seq.begin());
        insert_node(fnode);
        if(seq.size() == 1){
            return fnode;
        }
    }
}
void cal_weight(int &ans,HT* node,int level){
    if(node == NULL) return;
    if(node->lchild == NULL && node->rchild == NULL){
        ans = ans + node->data * level;
        return;
    }
    cal_weight(ans,node->lchild,level+1);
    cal_weight(ans,node->rchild,level+1);
}
int main(){
    int ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        HT *node = (HT*) malloc(sizeof(HT));
        scanf("%d",&node->data);
        node->lchild = NULL;
        node->rchild = NULL;
        seq.push_back(*node);
    }
    sort(seq.begin(),seq.end(),cmp);
    HT* root = buildHT();
    cal_weight(ans,root,0);
    printf("%d",ans);
    return 0;
}

编辑于 2019-02-02 16:37:12 回复(0)
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * Created by fhqplzj on 17-2-19 at 下午8:03.
 */
public class Huff {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(n);
            for (int i = 0; i < n; i++) {
                priorityQueue.add(scanner.nextInt());
            }
            int result = 0;
            while (priorityQueue.size() > 1) {
                int a = priorityQueue.poll();
                int b = priorityQueue.poll();
                result += a + b;
                priorityQueue.add(a + b);
            }
            System.out.println(result);
        }
    }
}
优先队列
发表于 2017-02-19 20:07:52 回复(0)
#include <iostream>
#include <queue>
using namespace std;

struct cmp {
	bool operator() (const int & a, const int & b) {
		return a > b;
	}
};

int main() {
	//freopen("t.txt", "r", stdin);

	int n;
	while(cin>>n) {
		priority_queue<int, vector<int>, cmp> pq;
		for(int i = 0; i<n; i++) {
			int t;
			cin>>t;
			pq.push(t);
		}
		int res = 0;
		while(pq.size() > 1) {
			int a = pq.top(); pq.pop();
			int b = pq.top(); pq.pop();
			int c = a + b;
			res += c;
			pq.push(c);
		}
		cout<<res<<endl; 
	}
}

发表于 2017-02-24 10:16:12 回复(0)
//答案结果为非叶子节点数值之和
//直到最后只剩两个元素
#include <stdio.h>
#include <stdlib.h>

void sort(int *a, int start, int end);

int main() {
    int n;
    int result = 0;
    while(scanf("%d",&n) != EOF) {
        int nums[n];
        for(int i = 0; i < n; i++)
            scanf("%d",&nums[i]);
        for(int i = 0; i < n - 1; i++) {
            sort(nums, i, n);
            nums[i+1] = nums[i] + nums[i+1];
            result = result + nums[i+1];
        }
        printf("%d\n",result);
        result = 0;
    }
    return 0;
}

void sort(int *a, int start, int end) {
    for(int i = start; i < end; i++) {
        for(int j = i; j < end; j++) {
            if(a[i] > a[j]){
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}
发表于 2019-06-10 22:54:35 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int temp;
        //优先级队列  小顶堆
        priority_queue<int,vector<int>,greater<int>>q;
        while(n--)
        {
              cin>>temp;
              q.push(temp);
        }
        int sum = 0;
        while(q.size()>1)
        {
            int a =  q.top();
            q.pop();
            int b =  q.top();
            q.pop();
            q.push(a+b);
            sum  = sum+a+b;
        }
        cout<<sum<<endl;
        
    }
    return 0;
}

发表于 2019-04-26 11:34:16 回复(0)
#include<stdio.h>
#include<queue>//使用优先队列标准模板
using namespace std;

//定义小顶锥
priority_queue<int,vector<int>,greater<int>> Q;

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int x;
        for(int i=0;i<n;i++){
            scanf("%d",&x);
            Q.push(x);
        }
        
        int ans = 0;//必须初始化
        while(Q.size() > 1){
            //取出权值最小的两个结点
            int a = Q.top();
            Q.pop();
            int b = Q.top();
            Q.pop();
            
            ans += a+b;
            Q.push(a+b);
        }
        
        printf("%d\n",ans);
    }
    return 0;
}
发表于 2019-03-25 19:44:28 回复(0)
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
    struct node *lchild,*rchild;
    int weight;
}BTNode;
BTNode *createHufftree(BTNode **f,int n)
{
    int loop,i,k1,k2;
    BTNode *pa;
    for(loop=1;loop<n;loop++){
        for(k1=0;k1<n&&!f[k1];k1++);
        for(k2=k1+1;k2<n&&!f[k2];k2++);
        for(i=k2;i<n;i++){
             if(f[i]){
                 if(f[i]->weight<f[k1]->weight){
                     k2=k1;
                     k1=i;
                 }
                 else if(f[i]->weight<f[k2]->weight)
                     k2=i;
             }
        }
        pa=(BTNode *)malloc(sizeof(BTNode));
        pa->lchild=f[k1];
        pa->rchild=f[k2];
        pa->weight=f[k1]->weight+f[k2]->weight;
        f[k1]=pa;
        f[k2]=NULL;
    }
    return f[k1];
}
int  Print(BTNode *root,int n){
    int count=0;
    BTNode *p=root;
    if(!p->lchild&&!p->rchild)
    {
        return p->weight*n;
        
    }
    else{
            count=Print(p->lchild,n+1)+Print(p->rchild,n+1);
            return count;
        
    }
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
         BTNode **f;
        int w,sum;
        f=(BTNode **)malloc(n*sizeof(BTNode *));
        for(int i=0;i<n;i++)
        {
            f[i]=(BTNode *)malloc(sizeof(BTNode));
            f[i]->lchild=f[i]->rchild=NULL;
            scanf("%d",&w);
            f[i]->weight=w;
        }
        //创建haffmantree
        BTNode *root=createHufftree(f,n);
        //输出权值
        sum=Print(root,0);
        printf("%d\n",sum);
    }
}
发表于 2019-03-21 17:35:16 回复(0)
#include<stdio.h>
#include<queue>

using namespace std;

priority_queue<int ,vector<int>,greater<int > > q;
int main()
{
    int n;
    int x;
    while(scanf("%d",&n)!=EOF)
    {
        while(!q.empty()) q.pop();
        for(int i=0;i<n;i++)
        {
            scanf("%d",&x);
            q.push(x);
        }
        int ans=0;
        while(q.size()>1)
        {
            int a=q.top();
            q.pop();
            int b=q.top();
            q.pop();
            ans+=a+b;
            q.push(a+b);
        }
        printf("%d",ans);
    }
    return 0;
}
发表于 2019-03-19 13:11:55 回复(0)
#include<bits/stdc++.h> 
#define N 1001
//求哈夫曼树的值不用建树也可计算(简化版),sum为所有非叶节点的和,即每次合并的开销和 
using namespace std;
struct cmp{
    bool operator()(int a,int b){
        return a>b;
    }
};
priority_queue<int,vector<int>,cmp> minHeap;//注意greater后的空格 
void initHeap(){
    while(!minHeap.empty()){
        minHeap.pop();
    }
}
void run(){
    int n,val,m1,m2,sum=0;
    scanf("%d",&n);
    initHeap();
    for(int i=0;i<n;i++){
        scanf("%d",&val);
        minHeap.push(val);
    }
    while(minHeap.size()>1){
        m1=minHeap.top();
        minHeap.pop();
        m2=minHeap.top();
        minHeap.pop();
        sum=sum+m1+m2;
        minHeap.push(m1+m2);
    }
    printf("%d\n",sum);
}
int main(){
    run(); 
    return 0;
}

//求哈夫曼树的值不用建树也可计算(简化版),sum为所有非叶节点的和,即每次合并的开销和

发表于 2019-03-16 22:05:41 回复(0)
//算法思想:对于本题,虽然是树结构,但是我们没有必要构造一树,完全可以使用优先队列
//这种数据结构解决本类问题。这是一个物理结构为线性,逻辑结构为树形的典型例子。
//首先,设置队列的优先级,使得队列从小到达排列。最小的两个元素出队,然后将这两个元素
//的和入队,定义ans记录每次加完的值即为最后的权值。直至队列只剩最后一个元素。
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int main(int argc, char const *argv[])
{
    //使用优先队列实现哈夫曼树的构造。
    priority_queue<int, vector<int>, greater<int> > q;
    int num;
    while(scanf("%d",&num)!=EOF)
    {
        int temp,a,b,ans=0;
        for (int i = 0; i < num; ++i)
        {
            scanf("%d",&temp);
            q.push(temp);
        }
        while(q.size()>1)//若队列里边还有两个以上元素,则继续进行权值相加
        {
            a=q.top();//记录最小元素的值
            q.pop();//出队
            b=q.top();//同上
            q.pop();
            ans+=a+b;
            q.push(a+b);
        }
        printf("%d\n", ans);
    }
    return 0;
}


发表于 2019-03-16 21:14:55 回复(0)
#include<stdlib.h>
#include<stdio.h>

int cmp(const void* a, const void* b){
    return *(int*)a-*(int*)b;
}
int main(){
    int n, weight[1000], sum=0;
    int i,j,k;
    scanf("%d", &n);
    for(i=0; i<n; i++){
        scanf("%d", &weight[i]);
    }
    for(i=0; i<n-1; i++){
        qsort(weight+i, n-i, sizeof(int), cmp);
        sum+=(weight[i]+weight[i+1]);
        weight[i+1]=weight[i]+weight[i+1];
    }
    printf("%d\n", sum);
    return 0;
}

发表于 2019-03-14 13:33:30 回复(0)