题解 | #哈夫曼树#

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct Tnode {
  int value;
  struct Tnode* lchild;
  struct Tnode* rchild;
} Tnode;

void bubblesort(Tnode* a, int len) { //冒泡排序
  for (int i = len; i > 1; i--) {
    for (int j = 0; j < i - 1; j++) {
      if (a[j].value < a[j + 1].value) {
        Tnode temp;
        temp = a[j + 1];
        a[j + 1] = a[j];
        a[j] = temp;
      }
    }
  }
}
int count(Tnode* a, int weight) { //递归求带权长度和
  if (a->lchild == NULL) {

    return weight * (a->value);
  }

  weight ++;
  int sum = count(a->lchild, weight) + count(a->rchild, weight);
  return sum;
}
int main() {
  int n;
  while (scanf("%d\n", &n) != EOF) {
    Tnode a[n];
    for (int i = 0; i < n; i++) {
      a[i].lchild = a[i].rchild = NULL;
      scanf("%d", &a[i].value);
    }
    while (n > 1) {
      bubblesort(a, n);
      Tnode* x = (Tnode*)calloc(1, sizeof(Tnode));
      x->value = a[n - 1].value + a[n - 2].value;
      Tnode* l = (Tnode*)calloc(1, sizeof(Tnode));
      Tnode* r = (Tnode*)calloc(1, sizeof(Tnode));
      l->value = a[n - 1].value;
      l->lchild = a[n - 1].lchild;
      l->rchild = a[n - 1].rchild;
      r->value = a[n - 2].value;
      r->lchild = a[n - 2].lchild;
      r->rchild = a[n - 2].rchild;
      x->lchild = l;
      x->rchild = r;
      a[n - 2] = *x;
      n--;
    }
    //    int sum=count(a,0);
    printf("%d", count(a, 0));
  }
}