Las operaciones en árboles son casi las mismas que para las listas:
Añadir elementos:
Recorrer el árbol completo.
Borrar árbol.
Búsqueda de un elemento
Añadir elementos.
Por lo regular los elementos en un árbol se insertan de tal forma que queden ordenados. En esta sección analizaremos cómo insertar elementos utilizando el recorrido en orden.Suponemos que se van a insertar los siguientes elementos:
14-16-2-17-15
Inserción del nodo 14: Como no existen elementos en el árbol, el nodo 14será la raíz.
Inserción del nodo 16: Para insertar este nodo recorremos el árbol en orden y además buscamos que el elemento quede ordenado. Es decir:
Nodo a insertar menor que el padre: Lo insertamos a la izquierda.
Nodo a insertar mayor que el padre: Lo insertamos a la derecha.
En este ejemplo el nodo 16 es mayor que el padre por lo tanto lo insertamos a la derecha
Inserción del nodo 2: El elemento 2 es menor que el padre por lo tanto es insertado a la izquierda.
Inserción del nodo 17: Como recordaremos el recorrido del árbol se hace en orden por lo tanto:
- El nodo es mayor que la raíz y se insertará a la derecha
- Encontramos que a la derecha ya existe el nodo 16 y que el nodo 17 es mayor, por lo tanto, hacemos el mismo procedimiento que en el paso 1 es decir, insertamos el elemento a derecha del nodo 16.
Inserción del nodo 15:
- El nodo 15 es mayor que la raíz, por lo que la inserción se realizará por la derecha.
- Llegamos al nodo 16 y de nuevo verificamos si es mayor o menor que el nodo a insertar, como se detecta que es menor se inserta a la izquierda.
Tal vez te preguntarás:
¿Por qué complicarse tanto al insertar los elementos en el árbol? Podríamos insertarlos conforme vayan llegando sin seguir un recorrido.
La respuesta es sencilla: el insertarlos de esta forma, permite ordenar los elementos del árbol al recorrerlo. Por lo que al hacer un recorrido en orden obtendremos los elementos ordenados.
2-14-15-16-17
Comentarios: Como habrás detectado para insertar se hacen tareas repetitivas hasta encontrar el lugar adecuado para el nodo, para representar inserción de árboles en un lenguaje de programación se puede usar un código iterativo hasta llegar a un nodo desocupado pero este código se vuelve muy complicado, una forma sencilla de insertar los elementos es hacer uso de un algoritmo recursivo. Por lo que te recomiendo recordar el tema recursividad usando pilas ubicado en el Módulo 1.
Como ya hemos analizado la forma en la que se añaden elementos en un árbol, ahora sí podemos desarrollar el código en lenguaje C para insertar elementos en un árbol. Este algoritmo será recursivo, debido a que es más sencillo de codificar que el iterativo.
Inserción de nodos en lenguaje C: Al insertar los elementos se usa una función recursiva con dos parámetros (un apuntador a la raíz y el valor a insertar). El algoritmo es:
- Si raíz es nulo
- Crear el nuevo nodo;
- En el campo información asignar el valor que recibimos como parámetro;
- Los apuntadores a izquierda y derecha se inicializan con nulo;
- raíz=nuevo.
- Si el apuntador no es nulo
- Si la raíz en su campo información es mayor al valor que se recibió como parámetro (indica que el elemento es menor; por lo tanto, se insertará por la izquierda);
- Llamar a la misma función de forma recursiva con los parámetros raíz ->izquierda;
- Si la raíz en su campo información es menor al valor que se recibió como parámetro (indica que el elemento es mayor; por lo tanto, se insertará por la derecha);
- Llamar a la misma función de forma recursiva con los parámetros raíz ->derecha;
- Si la raíz en su campo información es mayor al valor que se recibió como parámetro (indica que el elemento es menor; por lo tanto, se insertará por la izquierda);
| void inserta(arbol_binario*&raiz,intvalor) { arbol_binario*nuevo; if(!raiz) { //creamos el nodo nuevo=(arbol_binario*)malloc(sizeof(arbol_binario)); nuevo->info=valor; nuevo->izq=NULL; nuevo->der=NULL; raiz=nuevo//para poner elnuevo nodo en su lugar } else { if(raiz->info>=valor) inserta(raiz->izq, valor);//el nuevonodo se insertará por la izquierda else inserta(raiz->der, valor);//el nuevonodo se insertará por la derecha } return; } |
Recorrido del árbol:
Como ya vimos en el tema anterior, los árboles pueden ser recorridos en orden previo, en orden, y en orden posterior. El código para realizar cada una de estas operaciones es:
Recorrido en orden previo
| void orden_previo(arbol_binario*raiz) { if(raiz)//sitodaviaexisten nodos hacia abajo { printf("%d",raiz->info); orden_previo(raiz->izq); orden_previo(raiz->der); } return0; } |
Recorrido en orden
void orden(arbol_binario*raiz) |
Recorrido en orden posterior
| void orden_posterior(arbol_binario*raiz) { if(raiz)//sitodaviaexisten nodos hacia abajo { printf("%d",raiz->info); orden_posterior(raiz->der); orden_posterior(raiz->izq); } return0; } |
Borrar árbol:
Así como un árbol puede ser creado, también es posible eliminar cada uno de los nodos que lo componen.
| void destruye(arbol_binario*&raiz) { if(raiz) { destruye(raiz->izq); destruye(raiz->der); free(raiz); raiz=NULL; } } |
Buscar un elemento:
Una de las ventajas que tienen los árboles respecto de otras estructuras como listas, pila o colas, es la eficiente búsqueda de elementos, debido a que los elementos en un árbol se pueden insertar ordenados. En los arreglos las búsquedas se pueden hacer eficientemente si el arreglo se encuentra ordenado, pero la inserción y eliminación resultan costosas. Por el contrario, en las listas, dichas operaciones se pueden realizar fácilmente, pero la búsqueda no es eficiente, porque incluso en una búsqueda nos puede llevar recorrer todo el árbol (si el elemento buscado se encuentra en último lugar).
Cuando buscamos siempre tenemos tres opciones:
Opción a) Buscar por la izquierda (Si el elemento a buscar es < que el nodo padre);
Opción b) Buscar por la derecha (Si el elemento a buscar es > que el nodo padre);
Opción c) Mostrar los datos del nodo (Si el elemento a buscar es igual al nodo padre).
Ejemplo: Suponemos que deseamos buscar el elemento 17 en el árbol:
- Como el 17 es mayor que el nodo padre (14) buscaremos por la derecha;
- Llegamos al nodo padre 16 y como el 17 es mayor de nuevo buscaremos por la derecha;
- Ahora el 17 es el nodo padre: ¡¡lo hemos encontrado!!
| void busqueda(arbol_binario *&raiz, int dato) { if(dato < raiz->info) { if(raiz->izq == 0) printf("El nodo no se encuentra en el arbol"); else busqueda(raiz->izq, dato); } else { if(dato > raiz->info) { if(raiz->der ==NULL) printf("El nodo no se encuentra "); else busqueda(raiz->der, dato); } else { if(raiz->info ==dato) { printf("DATO ENCONTRADO ES %d ", raiz->info); return; } else printf("El nodo no se encuentra "); } } } |
