ÁRBOLES BINARIOS DE BÚSQUEDA
DEFINICIÓN
EVALUAR EXPRESIÓN ARITMÉTICA
CREAR UN ÁRBOL
EVALUACIÓN POSTFIJA
ÁRBOL BINARIO
TAD ABB
CREAR CON CLAVE
INSERCIÓN DE NODO
CREACIÓN DE UN ABB
BÚSQUEDA DE UN NODO
ELIMINACIÓN DE NODO
representan expresiones en memoria
todos los operadores tienen dos operandos
expresión se transforma a la expresión posfija
crear un árbol de expresión
usar una pila y un árbol de caracteres
evaluar la expresión
operandos serán siempre nodos hoja del árbol
operadores serán nodos padre
ideal es recuperar los dos operandos
el operador, y ejecutar la opción
el árbol tiene un solo nodo y este almacena un operando
la evaluación es el valor de ese operando
elementos en un árbol
sirven para buscar elementos
ejecutar en ellos búsqueda binaria
nodos del árbol izquierdo almacenan valores mayores al de p
mismas operaciones que para un AB
nodos del árbol derecho almacenan valores menores al de p
reglas para
Insertar
Sacar
Buscar
el nodo ahora tiene un campo clave
cambian un poco las operaciones del nodo
a la derecha valores mayor a la raíz
a la izquierda valores menor a la raíz
devolver el nodo que la contiene
se comienza en la raíz
clave buscada es igual a la clave del nodo evaluado
clave buscada es mayor a la del nodo evaluado
insertar en la posición correcta
árbol debe mantener sus propiedades
parecido a la búsqueda
enlazar el nuevo nodo al árbol
el árbol debe mantener sus propiedades
el árbol debe reajustarse
buscar el nodo p que se va a eliminar
el nodo a eliminar tiene menos de dos hijos
subir el nodo hijo a la posición del nodo eliminado
ubicar el nodo q con la mayor de las claves menores
reemplazar contenido de p con el del nodo q
eliminar el nodo q que se encontró en el primer paso