Arbol Y Grafos

INSTITUTO TECNOLOGICO DE IGUALA
MATERIA: ESTRUCTURA DE DATOS
MAESTRO: SERGIO RICARDO ZAGAL BARRERA

ALUMNO: DAVID VALLADARES VILLALOBOS

CARRERA: INGENIERIA EN SISTEMAS COMPUTACIONALES

SEMESTRE: TERCER SEMESTRE

NUMERO DE CONTROL: 13670036

DEFINICIÓN DE ÁRBOL.
Un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un
conjunto de nodos conectados). Un nodo es launidad sobre la que se construye el árbol y
puede tener cero o más nodos hijos conectados a él. Se dice que un nodo es padre de
un nodo si existe un enlace desde hasta (en ese caso, también decimos que es hijo
de ). Sólo puede 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 comorama.
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

y

árboles

de raíces

con
elementos cada uno, puede construirse
estableciendo una relación padre-hijo entre
y cada una de las raíces de los
árboles. El árbol resultante de
nodos tiene como
raíz el nodo , los nodos
sonlos hijos de
y el conjunto de
nodos hoja está formado por la unión de los conjuntos hojas iniciales. A cada uno
de los árboles
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 la
sucesión haya una relación de parentesco, decimos que es un árbol recorrido. Existen dos
recorridos típicos para listar los nodos de un árbol:en profundidad y en anchura. En el
primer 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 su parte, antes de listar los nodos de nivel
(a
distancia
aristas de la raíz), se deben haber listado todos los de nivel . Otros
recorridos típicos del árbol sonpreorden, postorden e inorden:





El recorrido en preorden, también llamado orden previo consiste en recorrer en
primer lugar la raíz y luego cada uno de los hijos
en orden previo.
El recorrido en inorden, también llamado orden simétrico (aunque este nombre
sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar
, luego la raíz y luego cada uno de los hijos
enorden simétrico.
El recorrido en postorden, también llamado orden posterior consiste en recorrer en
primer lugar cada uno de los hijos
en orden posterior y por último
la raíz.

Finalmente, puede decirse que esta estructura es una representación del concepto de
árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico.
Un árbol es una estructura no lineal y de dos dimensiones de datos, conpropiedades
especiales. Los nodos de los árboles contienen dos o más enlaces.

ESTRUCTURAS DE ÁRBOL.
Terminologías utilizadas en árboles







Raíz - El nodo superior del árbol.
Padre - Nodo con hijos.
Hijo - Nodo descendiente de otro nodo.
Hermanos - Nodos que comparten el mismo padre.
Hojas - Nodos sin hijos.
Nivel - El nivel de un nodo está definido por 1+ el número de conexiones entre elnodo y la raíz.

PROCESAMIENTO DE UN ÁRBOL (HORIZONTAL, VERTICAL, MIXTO).
Se entiende por recorrido el tratamiento realizado para acceder a los diferentes nodos de
un árbol. El recorrido puede afectar a la totalidad de los nodos del árbol (recorrido
completo), por ejemplo si se desea conocer el número de nodos, o finalizar
anticipadamente en función de determinada/s circunstancia/s, por ejemplo alencontrar el
valor de una clave determinada. En cualquier caso, el recorrido se puede realizar
basándose en las siguientes modalidades:


Preorden. La clave se procesa en primer lugar. Posteriormente se realizan las
llamadas recursivas (por la izquierda y por la derecha).
Este tipo de recorrido es el más utilizado pues atiende a la estructura de organización
jerárquica del árbol. También es el...