前面說到了哈夫曼樹的創(chuàng)建，那下面一個重要的環(huán)節(jié)就是哈夫曼樹的排序問題。但是由于排序的內(nèi)容是數(shù)據(jù)結(jié)構(gòu)，因此形式上說，我們需要采用通用數(shù)據(jù)排序算法，這在我之前的博客里面已經(jīng)涉及到了（通用算法設(shè)計）。所以，我們所要做的就是編寫compare和swap兩個函數(shù)。通用冒泡代碼如下所示，

void bubble_sort(void* array[], int length, int (*compare)(void*, void*), void(*swap)(void**, void**))  
{  
    int outer;  
    int inner;  

    for(outer = length -1; outer >0; outer --){  
        for(inner = 0; inner < outer; inner ++){  
            if(compare(array[inner], array[inner + 1]))  
                swap(&array[inner], &array[inner + 1]);  
        }  
    }  

    return;  
}  

compare和swap代碼如下所示，

int compare (void* a, void* b)  
{  
    HUFFMAN_NODE* node1 = (HUFFMAN_NODE*)a;  
    HUFFMAN_NODE* node2 = (HUFFMAN_NODE*)b;  

    return node1->frequence > node2->frequence ? 1 : 0;  
}  

void swap(void** a, void** b)  
{  
    HUFFMAN_NODE* median;  
    HUFFMAN_NODE** node1 = (HUFFMAN_NODE**)a;  
    HUFFMAN_NODE** node2 = (HUFFMAN_NODE**)b;  

    median = *node1;  
    *node1 = *node2;  
    *node2 = median;  
}  

有了創(chuàng)建函數(shù)和排序函數(shù)，那么哈夫曼樹就可以創(chuàng)建了，

HUFFMAN_NODE* create_huffman_tree(HUFFMAN_NODE* huffmanNode[], int length)  
{  
    HUFFMAN_NODE* head = NULL;  

    if(NULL == huffmanNode ||  length <= 1)  
        return NULL;  

    while(length > 1){  
        bubble_sort((void**)huffmanNode, length, compare, swap);  
        head = create_new_node('\0',  huffmanNode[0]->frequence + huffmanNode[1]->frequence);  
        assert(NULL != head);  

        head->left = huffmanNode[0];  
        head->right = huffmanNode[1];  
        huffmanNode[0]->parent = head;  
        huffmanNode[0]->symbol = 1;  
        huffmanNode[1]->parent = head;  
        huffmanNode[1]->symbol = 0;  

        memmove(&huffmanNode[0], &huffmanNode[2], sizeof(HUFFMAN_NODE*) * (length -2));  
        huffmanNode[length -2] = head;  
        length --;  
    }  

    return head;  
} 

上面的代碼完整了寫出了huffman樹的創(chuàng)建過程，那么我們怎么知道符號的編碼是多少呢？這其實不難，因為根節(jié)點都知道了，我們只要按照自下而上的順序遍歷節(jié)點就可以打印出編碼，只不過編碼是逆序的而已，

void print_code_for_str(HUFFMAN_NODE* pNode, HUFFMAN_NODE* head)  
{  
    if(NULL == pNode || NULL == head)  
        return;  

    while(head != pNode){  
        printf("%d", pNode->symbol);  
        pNode = pNode->parent;  
    }  

    return;  
}  

如果對代碼本身還有懷疑，可以編譯一個測試用例驗證一下，

void test()  
{  
    HUFFMAN_NODE* node1 = NULL;  
    HUFFMAN_NODE* node2 = NULL;  
    HUFFMAN_NODE* node3 = NULL;  
    HUFFMAN_NODE* node4 = NULL;  

    HUFFMAN_NODE* test[] = {node1 = create_new_node('a', 0.1),  
        node2 = create_new_node('b', 0.2),  
        node3 = create_new_node('c', 0.3),  
        node4 = create_new_node('d', 0.4),  
    };  

    HUFFMAN_NODE* head = create_huffman_tree(test, sizeof(test)/sizeof(HUFFMAN_NODE*));  
    print_code_for_str(node1, head);  
    print_code_for_str(node2, head);  
    print_code_for_str(node3, head);  
    print_code_for_str(node4, head);  
}

總結(jié)：

（1）哈夫曼樹不復(fù)雜，如果手算可以成功，那么編程應(yīng)該也沒有什么問題

（2）復(fù)雜算法都是由小算法搭積木而成的，朋友們應(yīng)該在基本算法上打下堅實的基礎(chǔ)

（3）算法注意復(fù)用，這里就用到了原來講到的通用算法內(nèi)容