Interesting Huffman tree

        When we study data structures , It is inevitable to encounter problems related to Huffman tree , Xiaobian will take you to appreciate the charm of Huffman tree today .

One 、 Explanation of Huffman tree

         Given N The weight of N A leaf node , Construct a binary tree , If the weighted path length of the tree reaches the minimum , Call such a binary tree an optimal binary tree , Also known as Huffman tree (Huffman Tree). Huffman tree is the tree with the shortest weight path length , Nodes with larger weights are closer to the root .

Two 、 The construction of Huffman tree

1、 Arrange all nodes in order from small to large .

2、 Take out the two smaller nodes as the left and right nodes of the new binary tree , Be careful , Use the smaller node as the left child , The larger node acts as the right child .

3、 Reorder the newly generated binary tree nodes together with other nodes .

4、 Repeat step 1、2、3 Until there is only one node left , The only node is the Huffman tree we need to construct .

while(list->count>1){
		simpleselectsort(list);
		p = list->head->next;
		q = p->next;
		tempbtnode0 = p->btnode;
		tempbtnode1 = q->btnode;
        newbtnode = (struct btnode *) malloc(sizeof(struct btnode ));
		newbtnode->data = tempbtnode0->data + tempbtnode1->data;
		newbtnode->info = '*';
		newbtnode->leftchild = tempbtnode0;
		newbtnode->rightchild = tempbtnode1;
		p->btnode = newbtnode;
		p->next = q->next;
		free(q);
		list->count--;
	}

3、 ... and 、 Get Huffman code

         We use stack to recursively traverse binary tree , When the leaf node is reached , We output all the elements stored in the stack , You can get the reverse Huffman code of the leaf node . Here are the relevant steps and their codes ：

1、 When the left child of this node is not empty , Then we will first 0 Push to stack , Then visit the left child of the node , After the visit, we need to get the top element out of the stack ; When the left child of this node is empty , Just execute the following procedure .

2、 When the node is a leaf node , We will output the data stored in the stack ; When this node is not a leaf node , Just execute the following procedures in sequence ;

3、 When the right child of this node is not empty , Then we will first 1 Push to stack , Then visit the right child of the node , After the visit, we need to get the top element out of the stack ; When the right child of this node is empty , End this recursion .

void inordervisit(struct btnode *p,struct int_slink_stack *stack){
	if(p->leftchild != NULL){
		int_slink_stack_push(stack,0);
		inordervisit(p->leftchild,stack);
		int_slink_stack_pop(stack);
	}
	if(p->leftchild == NULL && p->rightchild == NULL){
		if((int_slink_stack_isempty(stack) == 0)){ 
			printf("data:%d->",p->data);
			struct int_slink_stack_node *q = stack->top;
			while(q != NULL){
				printf("%d",q->data);
				q = q->next;
			}
			printf("\n");
		}
	}
	if(p->rightchild != NULL){
		int_slink_stack_push(stack,1);
		inordervisit(p->rightchild,stack);
		int_slink_stack_pop(stack);
	}
}

Four 、 summary

         In fact, the establishment of Huffman tree is to select two smallest nodes each time and merge them into a new binary tree , Huffman coding is mainly about the problem of entering and leaving the stack when traversing the Huffman tree and the problem of outputting Huffman coding , As long as we solve these problems, we can get the Huffman code of leaf nodes .

Catalog

One 、 Explanation of Huffman tree

Two 、 The construction of Huffman tree

3、 ... and 、 Get Huffman code

Four 、 summary

---