Ingenieria

En ciencias de la informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construyeel árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólopuede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.
Contenido[ocultar]

1 Definición
2 Tipos de árboles
3 Operaciones de árboles. Representación
4 Uso de los árboles
5 Véase también
5.1 Algoritmos de búsqueda en árboles

[editar]Definición

Formalmente, podemos definir un árbol de la siguiente forma:

Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).

Un nuevo árbol a partir de un nodo nry k árboles A_1, A_2 \dots A_k de raíces n_1, n_2, \dots, n_k con N_1, N_2, \dots ,N_k elementos cada uno, puede construirse estableciendo una relación padre-hijo entre nr y cada una de las raíces delos k árboles. El árbol resultante de N = 1 + N_1 + \dots + N_k nodos tiene como raíz el nodo nr, los nodos n_1, n_2, \dots, n_k son los hijos de nr y el conjunto de nodos hoja está formado por launión de los k conjuntos hojas iniciales. A cada uno de los árboles Ai se les denota ahora subárboles de la raíz.

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de lasucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En elprimer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por...