Construction of Huffman tree

【 Huffman tree 】 When used n Nodes （ All of them are leaf nodes and each has its own weight ） When trying to build a tree , If the weighted path length of the constructed tree is the smallest , Call this tree “ The best binary tree ”, Sometimes called the “ Huffman tree ” perhaps “ Huffman tree ”.

【 Building principles 】 The node with large weight is close to the root , The node with small weight is far from the root .

【 Preliminary knowledge 】 Huffman tree is a binary tree , Only 0 Degree node sum 2 Degree node .

                      For having n0 A Huffman tree with leaf nodes , share 2*n0-1 Nodes .

【 Algorithm steps 】

1. initialization ,ht An array of former n individual weight The member variable is assigned a weight , All parents and left and right sons are assigned -1.

2. before n In the forest composed of nodes, the two nodes with the smallest weight are selected to form a new binary tree to replace the original two nodes .

3. repeat 2 Until there is only one binary tree left in the forest .

【 Case study 】

Input ：

7
5 2 9 11 8 3 7

Output ：

 Please enter the number of nodes ：7
 Please enter the weight of the node ：5 2 9 11 8 3 7
 Minimum subscript ：1      Minor subscript ：5
 Minimum subscript ：0      Minor subscript ：7
 Minimum subscript ：6      Minor subscript ：4
 Minimum subscript ：2      Minor subscript ：8
 Minimum subscript ：3      Minor subscript ：9
 Minimum subscript ：10     Minor subscript ：11
 Print the contents of the constructed Huffman array ：
weiht  parent  lchild  rchild
5       8       -1      -1
2       7       -1      -1
9       10      -1      -1
11      11      -1      -1
8       9       -1      -1
3       7       -1      -1
7       9       -1      -1
5       8       1       5
10      10      0       7
15      11      6       4
19      12      2       8
26      12      3       9
45      -1      10      11

The manual tree creation is as follows ：

  notes ： The code strictly follows that the weight of the left son is greater than that of the right son , Manual operation may produce different results , But the length of the root node is the same , The length of the shortest weighted path is the same .

Don't talk much , Code up ：

#include <stdio.h>

typedef struct node {
	int weight;
	int parent, lchild, rchild;
}HTNode;

void print(HTNode *ht, int n) {
	printf(" Print the contents of the constructed Huffman array ：\n");
	printf("weiht  parent  lchild  rchild\n");
	for(int i=0;i<2*n-1;i++) 
		printf("%d\t%d\t%d\t%d\n",ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
}

void creatht(HTNode* ht, int n) {
	int min1, min2;
	int lnode, rnode;
	for(int i=n;i<2*n-1;i++) {
		min1 = min2 = 0x7fffffff;
		lnode = rnode = -1;
		for(int k=0;k<i;k++) { // Find the two nodes with the smallest weight among the nodes whose parents have not been assigned a value, that is, the corresponding subscript 
			if(ht[k].parent == -1) {
				if(ht[k].weight < min1) {
					min2 = min1, rnode = lnode;
					min1 = ht[k].weight, lnode = k;
				} else if(ht[k].weight < min2) {
					min2 = ht[k].weight, rnode = k;
				}
			}
		}
		printf(" Minimum subscript ：%d\t",lnode);
		printf(" Minor subscript ：%d\n",rnode);
		ht[i].weight = ht[lnode].weight + ht[rnode].weight; // Create subscript as i The new node 
		ht[i].lchild = lnode, ht[i].rchild = rnode;
		ht[lnode].parent = ht[rnode].parent = i; // The parents of the left and right sons are assigned a new node  
	}
	print(ht, n);
}

int main() {
	int n;
	printf(" Please enter the number of nodes ："); // initialization  
	scanf("%d",&n);
	printf(" Please enter the weight of the node ：");
	HTNode ht[2*n-1];
	for(int i=0;i<n;i++)
		scanf("%d",&ht[i].weight);
	for(int i=0;i<2*n-1;i++) 
		ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
	creatht(ht, n);
	return 0;
}