ARBOLES








INTRODUCCIÓN………………………………………………………………….2
1. DEFNICIÓN………………………………………………………………..3
2. RECORRIDO………………………………………………………………3
3. PROPIEDADES……………………………………………………………4
a. DESCENDENTES Y ASCENDENTES
b. HOJAS
c. ALTURA DE UN NODO
d. ALTURA DE UN NODO “NIVEL”
e. PESO DE UN ARBOL
f. NODOS HERMANOS
4. ORDENAMIENTOS………………………………………………………..5
5. NOTACIÓN PREFIJA……………………………………………………...6
6.NOTACIÓN POSTFIJA…………………………………………………….7
7. EXTRAS……………………………………………………………………..8
8. CONCLUCÓN………………………………………………………………9
9. BIBLIIOGRAFÍA…………………………………………………………….10



























Un árbol es una colección de elementos llamados “nodos”, uno de los cuales es la “raíz”. Existe una relación de parentesco por la cual cada nodo tiene un y sólo un “padre”, salvo laraíz que no lo tiene. El nodo es el concepto análogo al de “posición” en la lista, es decir un objeto abstracto que representa una posición en el mismo, no directamente relacionado con el “elemento” o “etiqueta” del nodo. Formalmente, el árbol se puede definir recursivamente de la siguiente forma:
“Un nodo sólo es un árbol”
Si n es un nodo y T1, T2 Y Tk son árboles con raíces n1-nk entoncespodemos construir un nuevo árbol que tiene a n como raíz y donde n1- nk son “hijos” de n. También es conveniente postular la existencia de un “árbol vacío” que llamaremos

Consideremos el árbol que representa los archivos en un sistema de archivos.
Los nodos del árbol pueden ser directorios o archivos. En el siguiente ejemplo observaremos la cuenta anuser que contiene 3 subdirectorios: docs,programas y juegos, los cuales a su vez contienen una serie de archivos. En este caso la relación entre nodos hijos y padres corresponde a la de pertenencia: un nodo a es hijo de otro b.








Camino. Si n1; n2, nk es una secuencia de nodos tales que n1 es padre de n2 para i = 1…k -1, entonces decimos que esta secuencia de nodos es un “camino” , de manera que anuser, docs, m2.txt es uncamino, mientras que docs, anuser, programas no. (Coincidentemente en Unix se llama camino a la especificación completa de directorios que va desde el directorio raíz hasta un archivo, por ejemplo el camino correspondiente a m2.txt es /anuser/docs/m2.txt. La “longitud” de un camino es igual al número de nodos en el camino menos uno, por ejemplo la longitud del camino fanuser, docs, m2.txtg es 2.Notar que siempre existe un camino de longitud 0 de un nodo a sí mismo.










Descendientes y antecesores: Si existe un camino que va del nodo a al b entonces decimos que a es antecesor de b y b es descendiente de a. Estrictamente hablando, un nodo es antecesor y descendiente de sí mismo ya que existe camino de longitud 0. Para diferenciar este caso trivial, decimos que a esdescendiente (antecesor) propio de b si a es descendiente (antecesor) de b, pero a ≠ b Por ejemplo:
m1.txt es descendiente de anuser y juegos es antecesor de g2 en la figura No. 1.

Hojas: Un nodo que no tiene hijos es una “hoja” del árbol. (Recordemos que, por contraposición el nodo que no tiene padre es único y es la raíz.) En el ejemplo, los nodos e, f, h y d son hojas.

Altura de un nodo: Laaltura de un nodo en un árbol es la máxima longitud de un camino que va desde el nodo a una hoja. Por ejemplo, el árbol de la figura la altura del nodo c es 2. La altura del árbol es la altura de la raíz. La altura del árbol de la figura 3 es 3. Notar que, para cualquier nodo.

0; si n es una hoja
n altura(n) =
1 + maxs=hijo de n altura(s); si no lo es.



Profundidad de un nodo “Nivel”: La“profundidad” de un nodo es la longitud de único camino que va desde el nodo a la raíz. La profundidad del nodo g en la figura No. 3 es 2. Un “nivel” en el árbol es el conjunto de todos los nodos que están a una misma profundidad. El nivel de profundidad 2 en el ejemplo consta de los nodos e, f y g.
Peso de un árbol: Es el número de nodos que contiene el árbol. El peso de un árbol nulo es 0.El...