数据结构系列20 - 哈夫曼树 - C语言实现

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
/*************************************************************************
* File Name: huffmanTree.c
* Author: TyrantLucifer
* E-mail: TyrantLucifer@gmail.com
* Blog: https://tyrantlucifer.com
* Created Time: Wed 21 Jul 2021 08:57:59 PM CST
************************************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
int weight;
int parent;
int lchild;
int rchild;
}TreeNode;

typedef struct HFTree {
TreeNode* data;
int length;
}HFTree;

HFTree* initTree(int* weight, int length) {
HFTree* T = (HFTree*)malloc(sizeof(HFTree));
T -> data = (TreeNode*)malloc(sizeof(TreeNode) * (2 * length - 1));
T -> length = length;
for (int i = 0; i < length; i++) {
T -> data[i].weight = weight[i];
T -> data[i].parent = 0;
T -> data[i].lchild = -1;
T -> data[i].rchild = -1;
}
return T;
}

int* selectMin(HFTree* T) {
int min = 10000;
int secondMin = 10000;
int minIndex;
int secondIndex;
for (int i = 0; i < T -> length; i++) {
if (T -> data[i].parent == 0) {
if (T -> data[i].weight < min) {
min = T -> data[i].weight;
minIndex = i;
}
}
}
for (int i = 0; i < T -> length; i++) {
if (T -> data[i].parent == 0 && i != minIndex) {
if (T -> data[i].weight < secondMin) {
secondMin = T -> data[i].weight;
secondIndex = i;
}
}
}
int* res = (int*)malloc(sizeof(int)* 2);
res[0] = minIndex;
res[1] = secondIndex;
return res;
}

void createHFTree(HFTree* T) {
int* res;
int min;
int secondMin;
int length = T -> length * 2 - 1;
for (int i = T -> length; i < length; i++) {
res = selectMin(T);
min = res[0];
secondMin = res[1];
T -> data[i].weight = T -> data[min].weight + T -> data[secondMin].weight;
T -> data[i].lchild = min;
T -> data[i].rchild = secondMin;
T -> data[i].parent = 0;
T -> data[min].parent = i;
T -> data[secondMin].parent = i;
T -> length ++;
}
}

void preOrder(HFTree* T, int index) {
if (index != -1) {
printf("%d ", T -> data[index].weight);
preOrder(T, T -> data[index].lchild);
preOrder(T, T -> data[index].rchild);
}
}

int main() {
int weight[7] = {5,1,3,6,11,2,4};
HFTree* T = initTree(weight, 7);
createHFTree(T);
preOrder(T, T -> length - 1);
printf("\n");
return 0;
}