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
| //修改可用版
#include <iostream>
#include <stdio.h>
#define length 16
//#define NULL 0
using namespace std;
struct Tree
{
int data;
Tree *left;
Tree *right;
};
Tree *creatHT(char *arr)
{
Tree *pArr[length] = {NULL};
Tree *p = NULL, *root = NULL;
for (int i = 0; i < length; i++)
{
pArr[i] = (Tree *)malloc(sizeof(Tree));
pArr[i]->left = NULL;
pArr[i]->right = NULL;
pArr[i]->data = arr[i];
}
for (int i = 0; i < length - 1; i++)
{
for (int m = i; m < length - 1; m++)
{
for (int j = m + 1; j < length; j++)
{
if (pArr[m]->data > pArr[j]->data)
{
Tree *temp = pArr[m];
pArr[m] = pArr[j];
pArr[j] = temp;
}
}
}
int k = i;
Tree *p = root;
root = (Tree *)malloc(sizeof(Tree));
root->left = pArr[k];
root->right = pArr[k + 1];
root->data = pArr[k]->data + pArr[k + 1]->data;
pArr[k] = NULL;
free(pArr[k]);
pArr[k + 1] = root;
}
return root;
}
int countWPL(Tree *root, int height = 0)
{
Tree *temp = root;
if (temp->left == NULL && temp->right == NULL)
{
return temp->data * height;
}
else
{
return countWPL(temp->left, height + 1) + countWPL(temp->right, height + 1);
}
}
void HuffmanCoding(Tree *root, int len)
{
static int arr[10] = {0};
if (root == NULL)
{
return;
}
if (root->left == NULL)
{
printf("%c ", root->data);
for (int i = 0; i < len; i++)
{
cout << arr[i];
}
cout << endl;
return;
}
else
{
arr[len] = 0;
HuffmanCoding(root->left, len + 1);
arr[len] = 1;
HuffmanCoding(root->right, len + 1);
}
}
void traverse(const Tree *root)
{
const Tree *temp = root;
if (temp == NULL)
{
return;
}
if (temp->left != NULL)
{
traverse(temp->left);
}
cout << temp->data << endl;
if (temp->right != NULL)
{
traverse(temp->right);
}
}
int main()
{
char arr[] = {'a', 'b', 'c', 'a', 'a', 'a', 'a', 'b', 'b', 'c', 'c', 'c', 'c', 'c', 'c', 'd', 'd', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'f', 'f', 'f', 'f', 'f', 'f', 'f'};
creatHT(arr);
for (int i = 0; i < length; i++)
{
cout << arr[i] << endl;
}
Tree *root = creatHT(arr);
traverse(root);
int w = countWPL(root);
cout << "WPL:" << w << endl;
HuffmanCoding(root, 0);
}
|