Un árbol es una estructura no lineal
formada por un conjunto de nodos y un conjunto de ramas.
Tenemos un nodo especial llamado raíz.
Un nodo del que sale una rama se llama nodo de bifurcación o nodo rama. Un nodo
que no tiene ramas se llama nodo terminal o nodo hoja.
De cada nodo cuelgan nuevos nodos que
constituyen un nuevo árbol denominado
subárbol de la raíz. El número de
ramas de un nodo recibe el nombre de grado del nodo. Si la raíz tiene nivel 0, el nivel de un
nodo es igual a la distancia de ese nodo al nodo raíz. El nivel máximo se llama profundidad o
altura del árbol.
Árboles
binarios
Si limitamos los árboles en el sentido
de que cada nodo sólo pueda ser de grado 2, tendremos árboles binarios, en los que
podemos distinguir árbol derecho y árbol izquierdo.
A su vez, cada subárbol es un árbol
binario.
Ejemplo. Las fórmulas algebráicas,
debido a que los operadores que intervienen son operadores binarios, nos dan un ejemplo
de estructura de árbol binario. Por ejemplo:
(a+b*c)/(d-e/f)
Dada la definición de árbol binario,
resulta sencilla su representación en un ordenador.
Dispondremos de una variable raíz para
referenciar al árbol y cada nodo contendrá dos enlaces: izquierdo y derecho:
typedef struct datos nodo;
struct datos
{
nodo * izquierdo;
nodo * derecho;
};
Recorrido
de árboles binarios
Esencialmente se puede recorrer un
árbol binario de tres formas:
*Preorden: raíz, subárbol izquierdo,
subárbol derecho.
*Inorden: subárbol izquierdo, raíz,
subárbol derecho.
*Postorden: subárbol izquierdo,
subárbol derecho, raíz.
Si consideramos el esquema general de un árbol tal como muestra la figura siguiente,los recorridos se definen como sigue:
- El listado en preorden es:
- Si el árbol tiene un único elemento, dicho elemento es el listado en preorden.
- Si el árbol tiene más de un elemento,es decir,una estructura como muestra la figura 2,el listado en preorden es listar el nodo raíz seguido del listado en preorden de cada uno de los subárboles hijos de izquierda a derecha.
- El listado en inorden es:
- Si el árbol tiene un único elemento,dicho elemento es el listado en inorden.
- Si el árbol tiene una estructura como muestra la figura 2,el listado en inorden es listar el subárbol A1 en inorden,y listar el nodo raíz seguido del listado en inorden de cada uno de los subárboles hijos de izquierda a derecha restantes.
- El listado en postorden es:
- Si el árbol tiene un único elemento,dicho elemento es el listado en postorden.
- Si el árbol tiene una estructura como muestra la figura 2,el listado en postorden es listar en postorden cada uno de los subárboles hijos de izquierda a derecha seguidos por el nodo raíz.
- El listado por niveles es: desde i=0 hasta la altura h
del árbol,listar de izquierda a derecha los elementos de
profundidad i.Como podemos observar,un nodo n1
aparece antes que n2 en el listado por
niveles si la profundidad de n1 es menor
que la profundidad de n2 usando el orden de
los nodos definido anteriormente para el caso en que tengan la misma
profundidad.
Como ejemplo de listados veamos el resultado que se obtendría sobre el árbol A de la figura 3.
Los resultados de los listados de preorden,postorden e inorden son los siguientes:
El listado por niveles de este árbol es el siguiente:r,v,s,u,w,p,q,x,y,z.
Finalmente es interesante conocer que un árbol no puede,en general,recuperarse con uno solo de sus recorridos.Por ejemplo:Dada la lista en inorden:vwyxzrtupsq,los árboles de la figura 4 tienen ese mismo recorrido en inorde.
BIBLIOGRAFIA
http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/index.htm-419&source=hp&q=arboles+en+programacion+c.pdf&aq=f&aqi=&aql=&oq=&pbx=1&bav=on.2,or.r_gc.r_pw.&fp=5f12827f8e650db9&biw=1366&bih=680
+6
ReplyDelete