Á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