-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary_tree.py
401 lines (301 loc) · 13.5 KB
/
binary_tree.py
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
# -*- coding: utf-8 -*-
"""Binary Tree.ipynb
Automatically generated by Colaboratory.
Original file is located at
https://colab.research.google.com/drive/1dbSETppPrRfp34tVjIp4gkYnFk68Z3Sw
UNEB - Universidade do Estado da Bahia
Aluno. Rafael Roberto Coutinho da Cruz
Estrutura de Dados 2.
----------------------------------------------------------
Implementar um modelo com arvores que tenha as seguintes funcionalidades
- Inserir ( Regra binária - menor á esquerda e maior a direita )
- Buscar
- Percorrer (preOrdem, emOrdem, posOrdem)
- Identificar o NO máximo
- Identificar o NO minimo
- Retorna o número total de NÓS
- Retorna o número total de FOLHAS
- Identificar as FOLHAS
- Calcular a altura de NÓ
- Remorver um NÓ
--------------------------------------------------------------------------------
Classe NO:
"""
class No:
def __init__(self, key, dir, esq):
self.item = key
self.dir = dir
self.esq = esq
"""Classe Tree:"""
class Tree:
def __init__(self):
self.root = No(None,None,None)
self.root = None
#Inserir ( Regra binária - menor á esquerda e maior a direita )
def inserir(self, inserted):
novo = No(inserted,None,None) # cria um novo Nó
if self.root == None:
self.root = novo
else: # se nao for a raiz
atual = self.root
while True:
anterior = atual
if inserted <= atual.item: # ir para esquerda
atual = atual.esq
if atual == None:
anterior.esq = novo
return # fim da condição ir a esquerda
else: # ir para direita
atual = atual.dir
if atual == None:
anterior.dir = novo
return # fim da condição ir a direita
#Buscar
def buscar(self, chave):
if self.root == None:
return None # se arvore vazia
atual = self.root # começa a procurar desde raiz
while atual.item != chave: # enquanto nao encontrou
if chave < atual.item:
atual = atual.esq # caminha para esquerda
else:
atual = atual.dir # caminha para direita
if atual == None:
return None # encontrou uma folha -> sai
return atual # terminou o laço while e chegou aqui é pq encontrou item
#Percorrer (preOrdem, emOrdem, posOrdem)
def inOrder(self, atual): # In Ordem
if atual != None:
self.inOrder(atual.esq)
print(atual.item,end=" ")
self.inOrder(atual.dir)
def preOrder(self, atual): # Pre Ordem
if atual != None:
print(atual.item,end=" ")
self.preOrder(atual.esq)
self.preOrder(atual.dir)
def posOrder(self, atual): # Pos Ordem
if atual != None:
self.posOrder(atual.esq)
self.posOrder(atual.dir)
print(atual.item,end=" ")
def perCorrer(self): #Percorrer (preOrdem, emOrdem, posOrdem)
print(" Exibindo em ordem: ",end="")
self.inOrder(self.root)
print("\n Exibindo em pos-ordem: ",end="")
self.posOrder(self.root)
print("\n Exibindo em pre-ordem: ",end="")
self.preOrder(self.root)
#Identificar o NO máximo, Identificar o NO minimo
def noMaximo(self): #Identificar o NO máximo.
atual = self.root
anterior = None
while atual != None:
anterior = atual
atual = atual.dir
return anterior
def noMinimo(self): #Identificar o NO minimo.
atual = self.root
anterior = None
while atual != None:
anterior = atual
atual = atual.esq
return anterior
def noMaximoMinimo(self):# Print o NO máximo, minimo
print(" Valor maximo: %d" %(self.noMaximo().item))
print(" Valor minimo: %d" %(self.noMinimo().item))
#Retorna o número total de NÓS
def contarNos(self, atual):
if atual == None:
return 0
else:
return 1 + self.contarNos(atual.esq) + self.contarNos(atual.dir)
def noTotal(self): # Print número total de NÓS
print(" Quantidade de Nós: %d" %(self.contarNos(self.root)))
#Retorna o número total de Folhas
def folhas(self, atual):
if atual == None:
return 0;
elif atual.esq == None and atual.dir == None:
return 1;
else:
return self.folhas(atual.esq) + self.folhas(atual.dir)
def totalFolhas(self): #Print número total de Folhas
print(" Quantidade de folhas: %d" %(self.folhas(self.root)))
#Exibir Lista de Folhas
def listFolhas(self, atual):
if atual == None:
return 0;
elif atual.esq == None and atual.dir == None:
print(" Suas Folhas são: %d" %(atual.item))
return 1;
else:
return self.listFolhas(atual.esq) + self.listFolhas(atual.dir)
def listaFolhas(self):
print(" Total de Folhas: %d" %(self.listFolhas(self.root)))
# LEVeL DO NO -
def levelNo(self, chave):
count = 0
if self.root == None:
return None # se arvore vazia
atual = self.root # começa a procurar desde raiz
while atual.item != chave: # enquanto nao encontrou
count += 1;
if chave < atual.item:
atual = atual.esq # caminha para esquerda
else:
atual = atual.dir # caminha para direita
if atual == None:
return None # encontrou uma folha -> sai
print("Level do Nó: ", count)
return atual # terminou o laço while e chegou aqui é pq encontrou item
# altura do nó -
def altura(self, atual):
if atual == None or atual.esq == None and atual.dir == None:
return 0
else:
if self.altura(atual.esq) > self.altura(atual.dir):
return 1 + self.altura(atual.esq)
else:
return 1 + self.altura(atual.dir)
def alturaNo(self, chave):
print("\n Altura da arvore: %d" %(self.altura(arv.buscar(x))))
#REMOÇÂO ou apenas uma tentativa futil de atingir um objeto tão longe
# O sucessor é o Nó mais a esquerda da subarvore a direita do No que foi passado como parametro do metodo
def nosucessor(self, apaga): # O parametro é a referencia para o No que deseja-se apagar
paidosucessor = apaga
sucessor = apaga
atual = apaga.dir # vai para a subarvore a direita
while atual != None: # enquanto nao chegar no Nó mais a esquerda
paidosucessor = sucessor
sucessor = atual
atual = atual.esq # caminha para a esquerda
# *********************************************************************************
# quando sair do while "sucessor" será o Nó mais a esquerda da subarvore a direita
# "paidosucessor" será o o pai de sucessor e "apaga" o Nó que deverá ser eliminado
# *********************************************************************************
if sucessor != apaga.dir: # se sucessor nao é o filho a direita do Nó que deverá ser eliminado
paidosucessor.esq = sucessor.dir # pai herda os filhos do sucessor que sempre serão a direita
# lembrando que o sucessor nunca poderá ter filhos a esquerda, pois, ele sempre será o
# Nó mais a esquerda da subarvore a direita do Nó apaga.
# lembrando também que sucessor sempre será o filho a esquerda do pai
sucessor.dir = apaga.dir # guardando a referencia a direita do sucessor para
# quando ele assumir a posição correta na arvore
return sucessor
def remover(self, v):
if self.root == None:
return False # se arvore vazia
atual = self.root
pai = self.root
filho_esq = True
# ****** Buscando o valor **********
while atual.item != v: # enquanto nao encontrou
pai = atual
if v < atual.item: # caminha para esquerda
atual = atual.esq
filho_esq = True # é filho a esquerda? sim
else: # caminha para direita
atual = atual.dir
filho_esq = False # é filho a esquerda? NAO
if atual == None:
return False # encontrou uma folha -> sai
# fim laço while de busca do valor
# **************************************************************
# se chegou aqui quer dizer que encontrou o valor (v)
# "atual": contem a referencia ao No a ser eliminado
# "pai": contem a referencia para o pai do No a ser eliminado
# "filho_esq": é verdadeiro se atual é filho a esquerda do pai
# **************************************************************
# Se nao possui nenhum filho (é uma folha), elimine-o
if atual.esq == None and atual.dir == None:
if atual == self.root:
self.root = None # se raiz
else:
if filho_esq:
pai.esq = None # se for filho a esquerda do pai
else:
pai.dir = None # se for filho a direita do pai
# Se é pai e nao possui um filho a direita, substitui pela subarvore a direita
elif atual.dir == None:
if atual == self.root:
self.root = atual.esq # se raiz
else:
if filho_esq:
pai.esq = atual.esq # se for filho a esquerda do pai
else:
pai.dir = atual.esq # se for filho a direita do pai
# Se é pai e nao possui um filho a esquerda, substitui pela subarvore a esquerda
elif atual.esq == None:
if atual == self.root:
self.root = atual.dir # se raiz
else:
if filho_esq:
pai.esq = atual.dir # se for filho a esquerda do pai
else:
pai.dir = atual.dir # se for filho a direita do pai
# Se possui mais de um filho, se for um avô ou outro grau maior de parentesco
else:
sucessor = self.nosucessor(atual)
# Usando sucessor que seria o Nó mais a esquerda da subarvore a direita do No que deseja-se remover
if atual == self.root:
self.root = sucessor # se raiz
else:
if filho_esq:
pai.esq = sucessor # se for filho a esquerda do pai
else:
pai.dir = sucessor # se for filho a direita do pai
sucessor.esq = atual.esq # acertando o ponteiro a esquerda do sucessor agora que ele assumiu
# a posição correta na arvore
return True
"""Main:"""
#criando a arvore
arv = Tree()
print("_____Bynary Tree_____")
# var do menu
menu = 0
while menu != 10:
print("\n Entre com a opcao:")
print(" --- 1: Inserir") #Inserir ( Regra binária - menor á esquerda e maior a direita )
print(" --- 2: Buscar") #Buscar
print(" --- 3: Percorrer") #Percorrer (preOrdem, emOrdem, posOrdem)
print(" --- 4: Exibir NO máximo / minimo") #Identificar o NO máximo, Identificar o NO minimo
print(" --- 5: Total de NÓS") #Retorna o número total de NÒS
print(" --- 6: Lista / Total de FOLHAS") #Retorna as FOLHAS e o seu TOTAL
print(" --- 7: Calcular LVL de NÓ") #Calcular o level do Nó
print(" --- 8: Calcular Altura do NÓ ") # Calcular a altura do Nó
print(" --- 9: Remoção de NÓ ") # Faz a Remoção do Nó
print(" --- 10: Sair do programa") #Sair do programa
menu = int(input("-> "))
if menu == 1:
x = int(input(" Informe o valor -> "))
arv.inserir(x)
elif menu == 2:
x = int(input(" Informe o valor -> "))
if arv.buscar(x) != None:
print(" Valor Encontrado")
else:
print(" Valor nao encontrado!")
elif menu == 3:
arv.perCorrer()
elif menu == 4:
arv.noMaximoMinimo()
elif menu == 5:
arv.noTotal()
elif menu == 6:
arv.listaFolhas()
elif menu == 7:
x = int(input(" Informe o valor -> "))
if arv.levelNo(x) != None:
print(" Valor Encontrado")
else:
print(" Valor nao encontrado!")
elif menu == 8:
x = int(input(" Informe o valor -> "))
arv.alturaNo(x)
elif menu == 9:
x = int(input(" Informe o valor -> "))
if arv.remover(x) == False:
print(" Valor nao encontrado!")
elif menu == 10:
print("FIM")
break