BINARY_SEARCH_TREE_Leonardo_Leon/ABB.py at main · LeoLeon-coder/BINARY_SEARCH_TREE_Leonardo_Leon · GitHub

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
# ARBOL_BINARIO_DE_BUSQUEDA_Leonardo_Leon
 '''
 Se desea añadir varios métodos a la clase del Árbol Binario de Búsqueda de forma eficiente.
 Quiero optimizar el programa al máximo sin que este pierda su funcionalidad.
 '''
class Hoja:

    '''
    Esta clase asigna el dato a la variable que se le indique.
    A su vez, esta clase no pertenece al árbol, sino que se
    encarga de distribuir la información al área correspondiente.
    '''
    def __init__(self, dato=None):
        self.dato = dato
        self.izquierda = None
        self.derecha = None

'''
Cuando añades un nuevo elemento al árbol, no esperas que este tenga descendientes, por ello
sus hijos (derecho e izquierdo) = None. El dato inicial también es cero debido a que no hay
datos en el árbol.
'''

class ArbolBinarioBusqueda:
    def __init__(self):
        self.raiz = None

    def agregar_dato(self):
        dato = int(input('Ingrese el elemento: '))
        if self.raiz is None:
            self.raiz = Hoja(dato)
        else:
            self.acomodar(dato, self.raiz)

    def acomodar(self, dato, hoja_act):
        if dato < hoja_act.dato:
            if hoja_act.izquierda is None:
                hoja_act.izquierda = Hoja(dato)
            else:
                self.acomodar(dato, hoja_act.izquierda)
        elif dato > hoja_act.dato:
            if hoja_act.derecha is None:
                hoja_act.derecha = Hoja(dato)
            else:
                self.acomodar(dato, hoja_act.derecha)
        else:
            print('El valor ya está en el árbol.')

    def buscar_dato(self):
        dato = int(input('Busqueda: '))
        if self.raiz:
            akita = self.buscar(dato, self.raiz)
            if akita:
                print(dato, 'pertenece al árbol y se encuentra en:', akita)
            else:
                print(dato, 'no pertenece al árbol.')
        else:
            print('No se ha creado el árbol.')

    def buscar(self, dato, hoja_act):
        if dato > hoja_act.dato and hoja_act.derecha:
            return self.buscar(dato, hoja_act.derecha)
        elif dato < hoja_act.dato and hoja_act.izquierda:
            return self.buscar(dato, hoja_act.izquierda)
        elif dato == hoja_act.dato:
            return hoja_act

    def recorrer_arbol(self):
        print('Recorrido.')
        if self.raiz:
            self.orden(self.raiz)
        print()

    def orden(self, hoja_act):
        if hoja_act:
            self.orden(hoja_act.izquierda)
            print(hoja_act.dato, end=' ')
            self.orden(hoja_act.derecha)

    def eliminar_dato(self):
        dato = int(input('Eliminar: '))
        if self.buscar(dato, self.raiz):
            print(dato, 'fue eliminado del árbol.')
        else:
            print(dato, 'no pertenecía al árbol registrado.')
        self.borrar(self.raiz, dato)

    def borrar(self, hoja_act, dato):
        if hoja_act is None:
            return hoja_act
        elif dato < hoja_act.dato:
            hoja_act.izquierda = self.borrar(hoja_act.izquierda,dato)
        elif dato > hoja_act.dato:
            hoja_act.derecha = self.borrar(hoja_act.derecha,dato)
        else:
            if hoja_act.izquierda is None and hoja_act.derecha is None:
                hoja_act = None
            elif hoja_act.izquierda is None:
                return hoja_act.derecha
            elif hoja_act.derecha is None:
                return hoja_act.izquierda
            else:
                temp = self.min(hoja_act.derecha)
                hoja_act.derecha = self.borrar(hoja_act.derecha, temp)
                hoja_act.dato = temp
                self.borrar(hoja_act.derecha,temp)
        return hoja_act

    def min(self, hoja_act):
        if hoja_act != None:
            return self._min(hoja_act)
        else:
            return None

    def _min(self,hoja_act):
        if hoja_act.izquierda != None:
            return self._min(hoja_act.izquierda)
        else:
            return hoja_act.dato

ab = ArbolBinarioBusqueda()

while True:
    print()
    print('     ', 'Árbol Binario', '     ')
    print()
    print('(1) Agregar elemento.')
    print('(2) Buscar elemento.')
    print('(3) Recorrer árbol.')
    print('(4) Eliminar elemento.')
    print('(5) Salir.')
    opcion = int(input('Opción: '))
    if opcion == 1:
        ab.agregar_dato()
    elif opcion == 2:
        ab.buscar_dato()
    elif opcion == 3:
        ab.recorrer_arbol()
    elif opcion == 4:
        ab.eliminar_dato()
    elif opcion == 5:
        print('¡Hasta pronto!')
        break