CAPÍTULO 1 – TEMA 4 – Operaciones sobre un árbol binario.
Árbol binario de búsqueda
Consideraciones para construir el árbol: * El primer elemento se utiliza para crear el ‘nodo raíz’. * Los valores del árbol deben ser tales que pueda existir un orden. * Los valores del sub-árbol izquierdo, de cualquier nodo, son menores o iguales al valor del nodo. * Los valores del sub-árbol derecho, de cualquier nodo, son mayores al valor del nodo.
Pasos para construir el árbol binario de búsqueda: 1. Colocar el primer valor como raíz. 2. Comparar el siguiente valor con la raíz; * si es menor, se coloca por el lado izquierdo; * si es mayor, se coloca por el lado derecho. 3. Se comparan los siguientes valores con …ver más…

Pasos a realizar para esta asignación: (Hacer la representación secuencial). 1. Primero adjuntamos 70 como el siguiente elemento del árbol completo, es decir, hacemos que ÁRBOL[21]=70 Entonces 70 es el hijo derecho de ÁRBOL[10]=48. 2. Ahora buscamos el sitio adecuado para 70 en el montón como sigue: a. Comparamos 70 con su padre 48: como 70 es mayor que 48, intercambiamos 70 y 48; b. Compráramos 70 con, su nuevo padre, 55 : como 70 es mayor que 55, los intercambiamos; c. Comparamos 70 con, su nuevo padre, 88: como 70 no excede a 88, ITEM=70 ha llegado a su lugar adecuado. Nota: Se puede verificar que el anterior procedimiento siempre deja un árbol de montón al final. Eliminación de la raíz de un árbol de montón Pasos para eliminar la raíz de un árbol de montón: 1. Asignar la raíz a alguna variable ÍTEM. 2. Reemplazar el nodo a eliminar, con el último nodo (L) del árbol. De manera que sigue siendo un árbol completo, aunque no necesariamente un árbol de montón. 3. Re-amontonar: Hacer que L se mueva a la posición adecuada en el árbol, para que este sea finalmente un árbol de montón. << Comparar L con sus dos hijos e intercambiarlo por su hijo mayor, hasta llegar a la posición adecuada >>

Llamaremos H al árbol completo de la figura 14. Donde R=95 es la raíz y L=22 es el último nodo del árbol. Pasos a realizar para esta asignación: (Hacer la