Algoritmo Para Eliminar un Nodo en un Árbol Binario

por Violeta León

Algoritmo para eliminar un nodo en árbol binario:

1.   Padre = NULL
2.   Si el árbol está vacío: el elemento no está en el árbol, por lo tanto salimos sin eliminar ningún elemento.
3.   Si el valor del nodo raíz es igual que el del elemento que buscamos, estamos ante uno de los siguientes casos:
a.    El nodo raíz es un nodo hoja:
                     i.        Si 'Padre' es NULL, el nodo raíz es el único del árbol, por lo tanto el puntero al árbol debe ser NULL.
                   ii.        Si raíz es la rama derecha de 'Padre', hacemos que esa rama apunte a NULL.
                  iii.        Si raíz es la rama izquierda de 'Padre', hacemos que esa rama apunte a NULL.
                  iv.        Eliminamos el nodo, y salimos.
b.   El nodo no es un nodo hoja:
                     i.        Buscamos el 'nodo' más a la izquierda del árbol derecho de raíz o el más a la derecha del árbol izquierdo. Hay que tener en cuenta que puede que sólo exista uno de esos árboles. Al mismo tiempo, actualizamos 'Padre' para que apunte al padre de 'nodo'.
                   ii.        Intercambiamos los elementos de los nodos raíz y 'nodo'.
                  iii.        Borramos el nodo 'nodo'. Esto significa volver a (3), ya que puede suceder que 'nodo' no sea un nodo hoja.
4.   Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.

5.   Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.


Anuncio

Comentarios