考研数据结构练手一：生成哈夫曼树。

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node* left;
    struct node* right;
};

void freenode(struct node* n)
{
    if(n->left != NULL) freenode(n->left);
    if(n->right != NULL) freenode(n->right);
    free(n);
}

int calcwpl(struct node* n, int d)
{
    int wpl = 0;
    
    if(n->left == NULL && n->right == NULL)
        wpl = n->data * d;
    else
    {
        if(n->left != NULL)
                wpl += calcwpl(n->left, d+1);
        if(n->right != NULL)
                wpl += calcwpl(n->right, d+1);
    }
    return wpl;
}

int main(void)
{
    int n, i, j, min1, min2;
    struct node** roots;
    struct node* newroot;
    
    scanf("%d", &n);
    roots = (struct node**)calloc(sizeof(struct node*), n);

    for(i = 0; i < n; i++)
    {
        roots[i] = (struct node*)malloc(sizeof(struct node));
            scanf("%d",&(roots[i]->data));
            roots[i]->left = roots[i]->right = NULL;
    }
    
    for(j = 1; j < n; j++)
    {
        min1 = -1;
        min2 = -1;
        for(i = 0; i < n; i++)
        {
            if(roots[i] == NULL)
                continue;

            if(min1 == -1)
            {
                    min2 = min1;
                    min1 = i;
            }
            else if(roots[i]->data < roots[min1]->data)
            {
                    min2 = min1;
                    min1 = i;
            }
            else if(min2 == -1)
            {
                    min2 = i;
            }
            else if(roots[i]->data < roots[min2]->data)
            {
                    min2 = i;
            }
        }
        
        newroot = (struct node*)malloc(sizeof(struct node));
        newroot->left = roots[min1];
        newroot->right = roots[min2];
        newroot->data = roots[min1]->data + roots[min2]->data;
        if(min1 < min2)
        {
            roots[min1] = newroot;
            roots[min2] = NULL;
        }else{
            roots[min2] = newroot;
            roots[min1] = NULL;
        }
    }
    
    printf("WPL = %d\n", calcwpl(roots[0], 0));
    freenode(roots[0]);
    return;
}