arv_bin_2022

### Arvore Binaria Não Balanceada
# Estrutura Recursiva
###
class Nodo:
    """
    Nodo da arvore:
      filhos da esquerda e direita + dado (que pode ser qualquer objeto)
    """
    def __init__(self, dado):
        self.esq = None
        self.dir = None
        self.dado = dado

    def __str__(self):
        return str(self.dado)

    def __repr__(self):
        return str(self.dado)

    def numFilhos(self, alvo):
        num_filhos = 0
        if (alvo.esq is not None):
            num_filhos += 1

        if (alvo.dir is not None):
            num_filhos += 1

        return num_filhos

    def inserir(self, dado):
        """
        Insere um novo nodo com dados
        @param dado a ser inserido
        """

        ## Insere na sub-arvore da esquerda
        if dado < self.dado:
            if self.esq is None:
                # Cria um novo nodo (que sera a sub-arvore da esquerda)
                self.esq = Nodo(dado)
            else:
                self.esq.inserir(dado)

        ## Insere na sub-arvore da direita
        elif dado > self.dado:
            if self.dir is None:
                # Cria um novo nodo (que sera a sub-arvore da direita)
                self.dir = Nodo(dado)
            else:
                self.dir.inserir(dado)

    def buscar(self, alvo, pai=None):
        # retornar uma tupla contendo o nodo alvo e o pai
        if alvo == self.dado:
            return self, pai
        else:
            if alvo > self.dado:
                if self.dir is None:
                    return None, None
                return self.dir.buscar(alvo, self)
            elif alvo < self.dado:
                if self.esq is None:
                    return None, None
                return self.esq.buscar(alvo, self)

    def remover(self, alvo, raiz=None): # alvo = valor dentro do nodo
        if raiz is None:
            return raiz

        if alvo < raiz.dado:
            raiz.esq = self.remover(alvo, raiz.esq)
        elif alvo > raiz.dado:
            raiz.dir = self.remover(alvo, raiz.dir)
        else:
            if raiz.esq is None:
                return raiz.dir
            elif raiz.dir is None:
                return raiz.esq

            raiz.dado = self.sucessorEmOrdem(raiz.dir)
            raiz.dir = self.remover(raiz.dado, raiz.dir)

        return raiz

    def sucessorEmOrdem(self, raiz=None):
        menor = raiz.dado
        while raiz.esq is not None:
            menor = raiz.esq.dado
            raiz = raiz.esq
        return menor

    def maximo(self, raiz=None):
        if raiz is not None:
            self = raiz

        if self.esq is None and self.dir is None:
            return self.dado
        else:
            if self.dir is not None:
                return self.maximo(self.dir)

            return self.dado

    def minimo(self, raiz=None):
        if raiz is not None:
            self = raiz

        if self.esq is None and self.dir is None:
            return self.dado
        else:
            if self.esq is not None:
                return self.minimo(self.esq)

            return self.dado

    def imprimirDecrescente(self):
        """
        Imprime o conteudo da arvore na tela,
        usando travessia em-ordem REVERSA
        (reverse in-order | arv_dir - raiz - arq_esq)

        https://en.wikipedia.org/wiki/Tree_traversal#Reverse_in-order_(RNL)
        """
        if self.dir:
            self.dir.imprimirDecrescente()

        # Raiz
        print(self.dado)

        if self.esq:
            self.esq.imprimirDecrescente()

    def imprimirEmOrdem(self):
        """
        Imprime o conteudo da arvore na tela,
        usando travessia em-ordem (in-order | arv_esq - raiz - arq_dir)
        """
        # Sub-arvore da Esquerda
        if self.esq:
            self.esq.imprimirEmOrdem()

        # Raiz
        print(self.dado)

        # Sub-arvore da Direita
        if self.dir:
            self.dir.imprimirEmOrdem()

    def imprimirPreOrdem(self):
        # Raiz
        print(self.dado)

        # Sub-arvore da Esquerda
        if self.esq:
            self.esq.imprimirPreOrdem()

        # Sub-arvore da Direita
        if self.dir:
            self.dir.imprimirPreOrdem()

    def imprimirPosOrdem(self):
        # Sub-arvore da Esquerda
        if self.esq:
            self.esq.imprimirPosOrdem()

        # Sub-arvore da Direita
        if self.dir:
            self.dir.imprimirPosOrdem()

        # Raiz
        print(self.dado)

    def size(self, raiz=None):
        if raiz is None:
            return 0
        else:
            return 1 + self.size(raiz.esq) + self.size(raiz.dir)

    def size2(self, raiz=None):
        if raiz is None: # caso base
            return 0

        fila = []
        fila.append(raiz)

        count = 0
        while(len(fila) > 0):
            nodo = fila.pop(0)

            count = count + 1

            if nodo.esq is not None:
                fila.append(nodo.esq)

            if nodo.dir is not None:
                fila.append(nodo.dir)

        return count

def main():

    ## Inserindo...

    nums = [4, 6, 5, 7, 1]
    raiz = Nodo(nums[0]) # insere o 1o item

    for n in nums[1:]: # insere os demais itens
        raiz.inserir(n)

    # imprimir de maneira crescente
    raiz.imprimirEmOrdem()

    print("remover 4")
    raiz.remover(4, raiz)

    raiz.imprimirEmOrdem()

    # imprimir de maneira decrescente
    #raiz.imprimirDecrescente()

    #print(raiz.buscar(5))

    #print(raiz.maximo(raiz))

    #print(raiz.size(raiz))
    #print(raiz.size2(raiz))

    #raiz.imprimirPreOrdem()
    #raiz.imprimirEmOrdem()
    #raiz.imprimirPosOrdem()

if __name__ == "__main__":
    main()