Python Sobre o antecessor e sucessor de uma arvore binária

[Rafaelmos]

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.

[Visitante]

Algumas funções(métodos) e Classes, estão meio confusas, quanto a passar e receber de outras classes ou métodos informações, para montar a árvore, simplesmente voce tem o método antecessor(self,perc,pai):, ela pede ao menos(requerido) um argumento para 'pai' e eu não identifiquei de onde vem o valor que e onde ele teria que ser informado até chegar em no método antecessor que requer esse valor informado, manualmente ou por passagem, mas informando ele manualmente como um parâmetro posicional pai=10 por exemplo, ele dá outro erro de atributo seria assim:

antecessor = arvore.antecessor(50, pai=10)

print("Antecessor", antecessor)

o erro relatado é: AttributeError: 'int' object has no attribute 'direita' (objeto int não tem atributo direita)???

 

Bom ai como ví que seu código não tinha coerência, fui atrás do estudo de Árvore binária de busca e entender o conceito, https://pt.wikipedia.org/wiki/Árvore_binária_de_busca

 

No meio da leitura me lembrei de uma matéria da USP sobre Python e arvores binárias e fui dar uma Googada numa professora do CNPQ que fez um trabalho sobre isso e que eu tenho ela no meu Github e achei seu problema resolvido.

 

Acho que copiar e colar não seria bom apar seu aprendizado, mas você deve ler e ver onde errou ao comparar os dois códigos.

 

aqui está o que você procura: https://gist.github.com/divanibarbosa/a8662693e44ab9ee0d0e8c2d74808929

 

Bons estudos!