#include <iostream>
using namespace std;

typedef struct huffmannode 
{
    char code;
    int weight;
    struct huffmannode* left;
    struct huffmannode* right;
}Huffmannode;

typedef struct codelist
{
    Huffmannode* codelist;
    struct codelist* next;
}Codelist;

void Inser(Codelist* cl_head, Codelist* code_temp)
{
    Codelist* temp = cl_head;
    while (temp->next)
    {
        if (temp->next->codelist->weight < code_temp->codelist->weight)
            temp = temp->next;
        else
            break;
    }
    code_temp->next = temp->next;
    temp->next = code_temp;
}

Codelist* poplist(Codelist* cl_head)
{
    Codelist* temp;
    temp = cl_head->next;
    if (cl_head->next)
    {
        temp = cl_head->next;
        cl_head->next = temp->next;
    }
    return temp;
}

void print_list(Codelist* cl_head)
{
    Codelist*temp = cl_head->next;
    while (temp)
    {
        cout << temp->codelist->code <<":"<< temp->codelist->weight<<"----";
        temp = temp->next;
    }
    cout << endl;
}

void PostOrderTraverse(Huffmannode * cl_head) 
{
    if (cl_head) 
    {
        cout << cl_head->weight << "--";
        PostOrderTraverse(cl_head->left);//遍历左孩子
        PostOrderTraverse(cl_head->right);//遍历右孩子
        
        
    }
}

void freetree(Huffmannode* root)
{
    if (root)
    {
        freetree(root->left);
        freetree(root->right);
        delete root;
    }
}
void freelist(Codelist* head)
{
    Codelist* temp = head;
    while (temp)
    {
        head = head->next;
        delete temp;
        temp = head;
    }
}

int main()
{
    char code[] = {'a','b','c','d','e','f'};
    int weight[] = { 19,13,12,16,9,5 };
    Codelist* cl_head = new Codelist;
    cl_head->next = NULL;
    for (int i = 0; i < 6; i++)
    {
        Huffmannode* temp = new Huffmannode;
        temp->code = code[i];
        temp->weight = weight[i];
        temp->left = NULL;
        temp->right = NULL;

        Codelist* code_temp = new Codelist;
        code_temp->codelist = temp;
        code_temp->next = NULL;
        Inser(cl_head, code_temp);
    }
    print_list(cl_head);


    for (int i = 0; i < 5; i++)
    {
        Codelist* temp1 = poplist(cl_head);
        Codelist* temp2 = poplist(cl_head);
        Codelist* new_node_c = new Codelist;
        new_node_c->codelist = new Huffmannode;
        
        new_node_c->codelist->left = temp1->codelist;
        new_node_c->codelist->right = temp2->codelist;
        new_node_c->codelist->weight = temp1->codelist->weight + temp2->codelist->weight;

        delete temp1;
        delete temp2;
        Inser(cl_head, new_node_c);

    }
    print_list(cl_head);
    if (cl_head->next)
    {
        PostOrderTraverse(cl_head->next->codelist);
        freetree(cl_head->next->codelist);
        freelist(cl_head);
    }




    return 0;
}