哈夫曼树（霍夫曼树）又称为最优树.
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#include <stdio.h>#include <stdlib.h>#include <string.h>/* 哈夫曼树的结构体 */typedef struct stHuNode{ int data; //权值 struct stHuNode* lchild, *rchild;}HUNODE;/** 找出权值数组里面,最小的两个权值下标* 函数请参：HUNODE *pArray[] 存放节点的指针数组 int n 数组里面的元素个数 int* p1 存放最小权值的下标 int* p2 存放第二小权值的下标*/int findSmallData(HUNODE *pArray[] ,int n,int* p1, int* p2){ int index = 0; int fir_small = 0xffff, sec_small = 0xffff; if(pArray == NULL) { return 1; } for(index = 0; index < n; index++) { /* 当前的下标下面是有节点的*/ if(pArray[index] != NULL) { if(pArray[index]->data < fir_small) { sec_small = fir_small; fir_small = pArray[index]->data; *p2 = *p1; *p1 = index; } else if(pArray[index]->data < sec_small) { sec_small = pArray[index]->data; *p2 = index; } } } return 0;}/** 函数功能：构建哈夫曼树* 函数请参：int* a 权值数组 int n 这个数组里面有多少个数据*/HUNODE* createHuTree(int* a, int n) { int index = 0; int fir_small = 0, sec_small = 0; /* 定义一个指针数组,最大是100 */ HUNODE *pArray[100]; HUNODE *pNewNode = NULL; /* 先创建n个root节点*/ memset(pArray,0,sizeof(HUNODE)*n); for(index = 0; index < n; index++) { pNewNode = (HUNODE*)malloc(sizeof(HUNODE)); memset(pNewNode,0,sizeof(HUNODE)); pNewNode->data = a[index]; pNewNode->lchild = NULL; pNewNode->rchild = NULL; /* 把这个节点存放在指针数组中去 */ pArray[index] = pNewNode; } /* 构建哈夫曼树 */ for(index = 0; index < n-1; index++) { /* fir_small 存放最小权值的下标 sec_small存放第二个小的权值下标*/ findSmallData(pArray,n,&fir_small,&sec_small); /* 分配节点内存 */ pNewNode = (HUNODE*)malloc(sizeof(HUNODE)); memset(pNewNode,0,sizeof(HUNODE)); pNewNode->data = pArray[fir_small]->data + pArray[sec_small]->data; /* 最小的是左孩子，第二小的是右孩子 */ pNewNode->lchild = pArray[fir_small]; pNewNode->rchild = pArray[sec_small]; /* 把新的节点放入到指针数组里面去 */ pArray[fir_small] = NULL; pArray[sec_small] = pNewNode; } return pNewNode;}/* 前序遍历该二叉树 */void preOrderHuffMan(HUNODE* root){ if(root) { printf("%d ",root->data); preOrderHuffMan(root->lchild); preOrderHuffMan(root->rchild); }}int main(){ int a[4] = {7,5,2,4}; HUNODE* root = NULL; /* 构建哈夫曼树 */ root = createHuTree(a,4); /* 前序遍历 */ preOrderHuffMan(root); printf("\n"); return 0;} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/u010889616/article/details/48052567
