-
Notifications
You must be signed in to change notification settings - Fork 0
/
215.cpp
147 lines (119 loc) · 3.33 KB
/
215.cpp
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
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <vector>
#include <stack>
class Nodo
{
public:
int valor;
Nodo *filloEsquerdo;
Nodo *filloDereito;
Nodo(int val) : valor(val), filloEsquerdo(nullptr), filloDereito(nullptr) {}
};
class Arbore
{
private:
void posorde(Nodo *nodo)
{
if (nodo != nullptr)
{
posorde(nodo->filloEsquerdo);
posorde(nodo->filloDereito);
std::cout << nodo->valor << " ";
}
}
public:
Nodo *raiz;
Arbore() : raiz(nullptr) {}
// Insertamos un nodo como fillo esquerdo (-1), fillo dereito (1) ou raiz (0)
Nodo *insertar(Nodo *pai, int val, int pos)
{
Nodo *nodo = new Nodo(val);
if (pos == -1)
pai->filloEsquerdo = nodo;
else if (pos == 0)
raiz = nodo;
else if (pos == 1)
pai->filloDereito = nodo;
return nodo;
}
void posorde()
{
if (raiz != nullptr)
{
posorde(raiz->filloEsquerdo);
posorde(raiz->filloDereito);
std::cout << raiz->valor << "\n";
}
}
};
// Vai introducindo os fillos esquerdos do nodo que visita ata que non teña fillo esquerdo
// (momento no que o percorrido inorde e o preorde coinciden)
int profundizar_esquerda(std::vector<int> &rInorde, std::vector<int> &rPreorde, int i, int j, Arbore &arbore, Nodo *&n, std::stack<Nodo *> &pila)
{
while (rPreorde[i] != rInorde[j])
{
n = arbore.insertar(n, rPreorde[i + 1], -1);
pila.push(n);
i++;
}
return i;
}
int main()
{
// Desvincula a E/S entre C++ e C
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int nodo;
std::cin >> nodo;
while (nodo != -1)
{
std::vector<int> rInorde;
std::vector<int> rPreorde;
while (nodo != -1)
{
rPreorde.push_back(nodo);
std::cin >> nodo;
}
std::cin >> nodo;
while (nodo != -1)
{
rInorde.push_back(nodo);
std::cin >> nodo;
}
Arbore arbore;
// O primeiro nodo do recorrido en preorde é a raiz da arbore
Nodo *n = arbore.insertar(nullptr, rPreorde[0], 0);
// A idea e ir introducindo na arbore todos os fillos esquerdos
// ata que cheguemos a un nodo que non ten fillos esquerdos
// (primeiro nodo do percorrido inorde).
// Na pila imos almacenando todos estes nodos que teñen fillos esquerdos
// incluído o último nodo introducido na arbore, que non ten fillo esquerdo.
size_t i = 0, j = 0;
std::stack<Nodo *> pila;
// Introducimos a raiz na pila
pila.push(n);
// Profundizamos pola esquerda ata que atopemos o primeiro nodo do percorrido inorde
i = profundizar_esquerda(rInorde, rPreorde, i, j, arbore, n, pila);
j++;
while (j < rInorde.size()) // Profundizamos pola esquerda con todos os fillos dereitos dos nodos da pila
{
n = pila.top();
pila.pop();
// Primeira condicion: Se e igual, o nodo n non ten fillo dereito
// Segunda condicion: Caso especial: Comprobamos se ten fillo dereito a raiz da arbore
if ((!pila.empty() && (pila.top()->valor != rInorde[j])) || (pila.empty() && (i < rPreorde.size())))
{
i++;
// Metemos o fillo dereito na arbore e na pila
n = arbore.insertar(n, rPreorde[i], 1);
pila.push(n);
i = profundizar_esquerda(rInorde, rPreorde, i, j, arbore, n, pila);
}
j++;
}
arbore.posorde();
// Lemos o inicio do seguinte caso
std::cin >> nodo;
}
return 0;
}