c에서 huffman 트리를 만드는 방법 (이미 정렬 된 배열이 있음)

Question

나는 허프만 트리를 만들려고하는데, 나는 이미 C 언어로 정렬 된 주파수 배열을 가지고있다.

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

및 주요 내부

() 내가 가진 :

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 새로운 노드. 두 개의 가장 낮은 주파수 노드를 가져 와서 새 노드의 왼쪽과 오른쪽에 할당하고 새 노드의 값에 주파수의 합을 넣습니다. 다른 요소를 아래로 이동하여 배열에서 두 노드를 삭제합니다. 이제 더 큰 요소를 하나 위로 이동시켜 value보다 작은 요소와 value보다 큰 요소 뒤에 배열에 새 노드를 삽입하십시오. 이제 배열에는 요소가 하나 더 적습니다.

배열에 요소가 하나만있을 때까지 반복하십시오. 그것은 나무의 근원입니다.

Answer 2

나는 예를 들어 최근에 HuffmanTree를 배우고 있는데, 주파수 배열이있다. 정렬 된 후에는 7,9,2,6,3이고, 정렬 된 후에는 2,3,6,7,9가된다. 당신은 항상 두 개의 배열의 요소, 그래서 2, 3 첫번째 선택 내 낮은 Scole의 ...에 대한 't 광고 사진,

5 
/\ 
2 3 

이 얻을하고 배열에 5를 추가하고 2 3.so을 삭제할 수 있습니다 배열은 지금 5,6,7,9 다음 단계는 5와 6을 선택이다, 그래서 당신이 얻을 수 있습니다

11 
    /\ 
    5 6 
/\ 
2 3 

그래서으로 5, 6, 광고 (11)을 삭제

16 
/\ 
7 9 

7과 9를 삭제하고, 지금은 11,16 11과 16를 선택입니다 배열로 (16)를 추가 : 지금 7,9,11 7과 9를 선택이다 배열은, 당신이 얻을 수 , 당신은 이것을 얻을 수있다 :

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