-
Notifications
You must be signed in to change notification settings - Fork 0
/
Treecode.cc
123 lines (101 loc) · 3.28 KB
/
Treecode.cc
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
/** @file Treecode.cc
@brief Implementación de la clase Treecode
*/
#include "Treecode.hh"
Treecode:: Treecode (){}
Treecode::Treecode(Tabla_frec& t){
struct sort {
bool operator() (const BinTree<pair <string, int> >a, const BinTree < pair <string, int> > b){
if (a.value().second!=b.value().second) return a.value().second<b.value().second;
return a.value().first<b.value().first;
}
};
set <BinTree <pair <string,int> >, sort > s;
t.it_begin();
int n = t.tamano();
for (int i=0; i<n; ++i){
s.insert(BinTree<pair<string,int> >(*(t.puntero())));
t.aumentar_it();
}
//CREAMOS LISTA DE BINTREES
while (s.size()!=1){
//CREAMOS A1 Y A2
BinTree < pair <string, int> > a1 = *(s.begin());
s.erase(s.begin());
BinTree < pair <string, int> > a2 = *(s.begin());
s.erase(s.begin());
//CREAMOS EL BINTREE b
string concat;
if (a1.value().first<a2.value().first)
concat = a1.value().first + a2.value().first;
else
concat = a2.value().first + a1.value().first;
int suma = a1.value().second + a2.value().second;
BinTree < pair <string, int> > b (make_pair(concat, suma), a1, a2);
//COLOCAMOS EL NUEVO BINTREE EN LA LISTA
s.insert(b);
}
this->tree = *(s.begin());
}
void Treecode:: imprimir_treecode_inorden(const BinTree<pair <string, int> >& a) const{
if (not a.empty()) {
imprimir_treecode_inorden(a.left());
cout << a.value().first << " " << a.value().second << endl;
imprimir_treecode_inorden(a.right());
}
}
void Treecode:: imprimir_treecode_preorden(const BinTree<pair <string, int> >& a) const{
if (not a.empty()) {
cout << a.value().first << " " << a.value().second << endl;
imprimir_treecode_preorden(a.left());
imprimir_treecode_preorden(a.right());
}
}
void Treecode:: escribir() const{
if (!tree.empty()){
//IMPRIMIR TREECODE EN PREORDEN
cout << "recorrido en preorden:" << endl;
imprimir_treecode_preorden (tree);
//IMPRIMIR TREECODE EN INORDEN
cout << "recorrido en inorden:" << endl;
imprimir_treecode_inorden (tree);
}
}
string Treecode::decodifica_rec(const string& palabra, BinTree< pair<string, int> > arbol, int& i, int& ultima_letra){
if (arbol.left().empty()) {
ultima_letra = i;
return (arbol.value().first);
}
else if (i == palabra.size()) {
return "0";
}
else if (palabra[i] == '0') {
++i;
return decodifica_rec(palabra, arbol.left(), i, ultima_letra);
}
// if (palabra[i] == '1')
else{
++i;
return decodifica_rec(palabra, arbol.right(), i, ultima_letra);
}
}
int Treecode::decodifica(string& palabra){
string decode;
int i = 0, n = palabra.length(), ultima_letra = 0;
while (i<n){
decode += decodifica_rec (palabra, tree, i, ultima_letra);
}
palabra = decode;
return ultima_letra;
}
void Treecode::crear_codigos_rec(Codigos & cod, const BinTree< pair<string,int> >& a, string codigo){
if (!a.left().empty())
crear_codigos_rec (cod, a.left(), codigo+"0");
if (!a.right().empty())
crear_codigos_rec (cod, a.right(), codigo+"1");
else if (a.left().empty() and a.right().empty())
cod.anadir_codigo(make_pair(a.value().first, codigo));
}
void Treecode::crear_cod_tree(Codigos & cod){
crear_codigos_rec(cod, tree, "");
}