c - 如何在c中创建霍夫曼树(已经有一个排序数组)

Question

我正在尝试创建一棵霍夫曼树，我已经有一个用 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

分配一个新节点。取频率最低的两个节点，将它们分配到新节点的左侧和右侧，并将它们的频率之和放入新节点的值中。通过向下移动其他元素来从数组中删除两个节点。现在，通过将较大的元素向上移动一位，将新节点插入到数组中小于 value 的元素之后和大于 value 的元素之前。数组现在少了一个元素。

重复此操作，直到数组中存在一个元素。那是树的根。