如何在c中創建一個huffman樹（已經有一個排序數組）

Question

我想創建一個Huffman樹，我已經有了一個用c語言編排的頻率數組。 這裏是我的結構：

struct node 
{ 
    int value; 
    char letter;     /* symbol */ 
    struct node *left,*right; /* left and right subtrees */ 
}; 
typedef struct node Node; 

和裏面的main（）我有：

int main(){ 
    Node *tree; 
    FILE *input, *output; //file input and output i am taking because i will take a input text file containing encoding of all 27 alphabets like a= 00001 b= 00010 etc. 

    buildHuffmanTree(&tree); // see it's function call there i already have done sorting of frequencies using qsort() BUT I DON'T KNOW WHAT TO DO AFTER. 
    return 0; 
} 

在這裏看到：

void buildHuffmanTree(Node **tree){ 
    Node *temp; 
    Node *array[27]; 
    int i, subTrees = 27; 
    int smallOne; 

    for (i=0;i<27;i++) 
    { 
     array[i] = malloc(sizeof(Node)); 
     array[i]->value = englishLetterFrequencies[i]; //this englishLetterFrequencies[27] contains the the frequencies of all 27 alphabtets like ={81,27,1,12.....up to 27 index of this array} 
     array[i]->letter = i; 
     array[i]->left = NULL; 
     array[i]->right = NULL; 
    } 
//here is the sorting part: 
int i = 0; int d,p; 
    printf("the array frequency is \n"); 
    for(d=0;d < 27;d++) 
    printf("%d ",array[d]->value); 
    // sorting of arrays 
    qsort(array,27,sizeof(*array),cmpfunc); 
    ////////////////////////// 
    printf("\n the sorted array frequency is \n"); 
     for(p=0;p < 27;p++) 
    printf("%d ",array[p]->value); //So now this array[p]->value contains all the sorted frequency. 
//I DON'T KNOW WHAT TO DO NOW 
return; 
} 

與有序陣列，我心目中是什麼

現在。 。首先，我將採用前兩個節點（位於增序排序數組[]的第一個和第二個索引中），然後添加它們並重新排序，並使用它形成樹。但我不知道鋤頭要這樣做。我是一個開始。任何人都可以解釋如何實現它？

Answer 1

Malloc一個新節點。取兩個最低頻率節點並將它們分配到新節點的左側和右側，並將它們的頻率之和設置爲新節點的值。通過向下移動其他元素來刪除陣列中的兩個節點。現在，通過將更大的元素向上移動一個元素，將小於值的元素之前和元素大於值之前的新節點插入到數組中。該數組現在有一個較少的元素。

重複，直到數組中有一個元素。這是樹的根。

Answer 2

我最近在學習HuffmanTree，例如：你有一個頻率數組，它是7,9,2,6,3，排序後它變成了2,3,6,7,9。我可以「T廣告圖片爲我的低斯科爾...... 你總是選擇第一個數組的兩個元素，所以2和3，

5 
/\ 
2 3 

，你可以得到它並添加5到您的陣列和刪除2和3.so陣列現在是5,6,7,9 下一步就是選擇5和6，這樣你就可以得到這樣的：

11 
    /\ 
    5 6 
/\ 
2 3 

所以刪除5和6，和廣告11到陣列，也就是現在的7,9,11 挑7和9，你可以得到這樣的：

16 
/\ 
7 9 

刪除7和9，並添加16到數組，這是現在11,16 挑選11和16 ，你可以得到：

 27 
    /\ 
    11 16 
    /\ /\ 
    5 6 7 9   
/\ 
2 3