class No:
def __init__(self, valor):
self.valor = valor
self.direita = None
self.esquerda = None
def __str__(self):
return str(self.valor)
class Arvore:
def __init__(self):
self.raiz = None
self.folhas = 0
def __addNo(self, no, perc):
if no.valor > perc.valor:
if perc.direita == None:
perc.direita = no
else:
self.__addNo(no, perc.direita)
elif no.valor < perc.valor:
if perc.esquerda == None:
perc.esquerda = no
else:
self.__addNo(no, perc.esquerda)
else:
raise ("Esse número ja existe")
def add(self, valor):
no = No(valor)
if self.raiz == None:
self.raiz = no
else:
self.__addNo(no, self.raiz)
self.folhas += 1
def __buscarNo(self, valor, perc, pai):
if perc == None:
return None, pai
if perc.valor == valor:
return perc, pai
else:
if valor > perc.valor:
return self.__buscarNo(valor, perc.direita, perc)
else:
return self.__buscarNo(valor, perc.esquerda, perc)
def buscar(self, valor):
if self.raiz == None:
return False
no, pai = self.__buscarNo(valor, self.raiz, None)
if no == None:
return False
return True
def __imprimir(self, perc):
if perc != None:
print(perc)
self.__imprimir(perc.esquerda)
self.__imprimir(perc.direita)
def imprimir(self):
self.__imprimir(self.raiz)
def antecessor(self, perc, pai):
if perc.direita == None:
return perc, pai
else:
self.antecessor(perc.direita, perc)
def sucessor(self, perc, pai):
if perc.esquerda == None:
return perc, pai
else:
self.sucessor(perc.esquerda, perc)
def remover(self, valor):
if self.raiz == None:
raise ("...")
no, pai = self.__buscarNo(valor, self.raiz, None)
if no == None:
raise ("...")
elif no.esquerda == None:
if pai == None:
self.raiz = self.raiz.direita
else:
if pai.esquerda == no.esquerda:
pai.esquerda = no.direita
else:
pai.direita = no.direita
elif no.direita == None:
if pai == None:
self.raiz = self.raiz.esquerda
else:
if perc.esquerda == no:
perc.esquerda = no.esquerda
else:
perc.direita = no.esquerda
else:
sucessor, sucessorPai = self.sucessor(no.direita, no)
no.valor = sucessor.valor
if sucessorPai == no.direita:
sucessorPai.direita = None
else:
sucessorPai.esquerda = None
self.folhas -= 1
arvore = Arvore()
arvore.add(10)
arvore.add(30)
arvore.add(70)
arvore.add(50)
arvore.add(200)
arvore.add(150)
arvore.add(300)
#arvore.remover(10)
#arvore.imprimir()
#print(arvore.buscar(150))
#print(arvore.folhas)
antecessor = arvore.antecessor(50)
print("Antecessor" , antecessor)
Bom galera do forum estou tentado, retornar a função do sucessor e antecessor dessa árvore, mas não estou sabendo como, não sei se é algum erro na codificação ou se estou tentando imprimir valor do sucessso/antecessor de maneira errada.
Vocês poderiam me indicar como posso corrigir essas funções se estiverem incorretas, ou me mostrar a forma correta de chama-las.