构造哈夫曼树（C语言）

电玩女神 2023-01-18 02:23 90阅读 0赞

哈夫曼树又称最优树，即带权路径长度最小的二叉树。

构造过程是典型的贪心算法，即每一步都求取最优情况使整体情况也达到最优。所以构造哈夫曼树时，应该让权重小的结点放在靠下的位置让权重大的放在较上的位置。

代码：

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define N 30     //叶子结点最大值
    #define M 2*N-1  //所有结点最大值
    
    typedef struct
    {
        
    	int flag;
    	int weight;
    	int parent, LChild, RChild;
    }HTNode, HuffmanTree[M + 1]; //0号单元不用
    
    void Select(HuffmanTree ht, int tmp, int* s1, int* s2);//找到ht中权值最小的两个结点
    void CreateHuffman(HuffmanTree ht, int w[], int n);   //构建哈夫曼树ht[M+1],w[]存放n个权值
    void PrintHuffman(HuffmanTree ht, int m);             //打印哈夫曼树
    
    
    int main()
    {
        
    	int n; //n个权值
    	scanf("%d", &n);
    	int *w;
    	w = (int*)malloc(sizeof(int) * (n+1));
    	if (w == NULL) {
        
    		return 0;
    	}
    	for (int i = 1; i <= n; i++) {
        
    		scanf("%d", &w[i]);
    	}
    	HuffmanTree ht;
    	CreateHuffman(ht, w, n);
    	PrintHuffman(ht, 2 * n - 1);
    	return 0;
    }
    
    void Select(HuffmanTree ht, int n, int* s1, int* s2)
    {
           //找到ht中权值最小的两个结点
    	int min = 0, tmp;
    	for (int i = 1; i <= n; i++) {
        
    	//找一个没有父节点的结点
    		if (ht[i].parent == 0) {
        
    			min = i;
    			tmp = ht[i].weight;
    			break;
    		}
    	}
    	for (int i = 1; i <= n; i++) {
        
    		if (ht[i].parent == 0 && ht[i].weight < tmp) {
        
    			min = i;
    			tmp = ht[i].weight;
    		}
    	}
    	*s1 = min;
    	ht[min].parent = -1;
    	for (int i = 1; i <= n; i++) {
        
    	//找一个没有父节点的结点
    		if (ht[i].parent == 0) {
        
    			min = i;
    			tmp = ht[i].weight;
    			break;
    		}
    	}
    	for (int i = 1; i <= n; i++) {
        
    		if (ht[i].parent == 0 && ht[i].weight < tmp) {
        
    			min = i;
    			tmp = ht[i].weight;
    		}
    	}
    	*s2 = min;
    }
    
    void CreateHuffman(HuffmanTree ht, int w[], int n)
    {
           //构建哈夫曼树ht[M+1],w[]存放n个权值
    	ht[0].flag = 0;
    	for (int i = 1; i <= n; i++) {
        
    	//将前n项初始化
    		ht[i].flag = ht[i - 1].flag + 1;
    		ht[i].weight = w[i];
    		ht[i].parent = 0;
    		ht[i].LChild = 0;
    		ht[i].RChild = 0;
    	}
    	int m = 2 * n - 1;
    	for (int i = n + 1; i <= m; i++) {
        
    	//将n+1项到m项初始化
    		ht[i].flag = ht[i - 1].flag + 1;
    		ht[i].weight = 0;
    		ht[i].parent = 0;
    		ht[i].LChild = 0;
    		ht[i].RChild = 0;
    	}
    	int s1, s2;
    	for (int i = n + 1; i <= m; i++) {
        
    	//开始构造
    		Select(ht, i-1, &s1, &s2);
    		ht[i].weight = ht[s1].weight + ht[s2].weight;
    		ht[i].LChild = s1;
    		ht[i].RChild = s2;
    		ht[s1].parent = i;
    		ht[s2].parent = i;
    	}
    }
    
    void PrintHuffman(HuffmanTree ht, int m)
    {
           //打印哈夫曼树
    	printf("结点\tweight\tparent\tLChild\tRChlid");
    	for (int i = 1; i <= m; i++) {
        
    		printf("\n%d\t%d\t%d\t%d\t%d",ht[i].flag, ht[i].weight, ht[i].parent, ht[i].LChild, ht[i].RChild);
    	}
    }