Arboles Con Ejemplos En Lenguaje C
Páginas: 15 (3542 palabras)
Publicado: 9 de octubre de 2011
Árbol General
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 construye el á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ó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 como rama.
Los árboles son una de las estructuras de datos no lineales más utilizada. Sirve para representar estructuras de información jerárquicas y direcciones o etiquetas de una manera organizada.
Aplicaciones de los Árboles GeneralesPor ejemplo:
* organizar tablas de símbolos en compiladores
* representar tablas de decisión
* asignar bloques de memoria de tamaño variable
* ordenar
* buscar
* solucionar juegos
* probar teoremas
Los árboles permiten representar situaciones de la vida diaria como son:
* organización de una empresa
* árbol genealógico de una persona
*organización de torneos deportivos
Definición: Un árbol es un conjunto finito T de uno o más nodos tal que:
a) Existe un nodo especial llamado la raíz de árbol
b) Los nodos restantes están particionados en m > 0 conjuntos disjuntos T1,...,Tm y cada uno de estos conjuntos es a su vez un árbol. Los árboles T1,...,Tm son llamados subárboles de la raíz
Cualquier nodo es la raíz de unsubárbol que consiste de él y los nodos debajo de él. Esto se deriva de la definición recursiva de árbol presentada.
Un árbol puede representarse gráficamente de muchas formas. Algunas de ellas son por medio de:
* conjuntos anidados:
* paréntesis anidados.
(1(2(4(9,10, 11),5),3(6(12),7,8)))
* indentación
* grafos
La forma más común de representar a los árboleses por medio de un grafo con la raíz hacia arriba:
Cada vértice o nodo del árbol puede tener un nombre y puede tener una información asociada; un arco es una conexión entre dos vértices.
Un camino en un árbol es una lista de vértices diferentes en los que vértices sucesivos están conectados por arcos en el árbol. Una propiedad que define a los árboles es que existe exactamente un caminoentre la raíz y cada uno de los otros nodos en el árbol.
La longitud de un camino es el número de nodos del camino menos uno. Por tanto, hay un camino de longitud cero de cualquier nodo a si mismo.
Se dice que un nodo Y está abajo de un nodo X, si X está en el camino de Y a la raíz. Además, cada nodo, excepto la raíz, tiene exactamente un nodo arriba de él, que es llamado su padre; los nodosque están exactamente abajo de él son llamados sus hijos.
El número de hijos que cuelgan de un nodo es llamado el grado del nodo. El grado de un árbol es el grado máximo de los nodos del árbol. Un nodo de grado cero es llamado hoja, es decir, no tiene hijos.
Ejemplo:
Considere el siguiente árbol:
El camino del nodo A al nodo P es (A, B, D, J, P), cuya longitud de camino es 4. E esel padre de K y L.
Los hijos de G son M, N y O.
Los nodos de grado 0 son: I, P, K, L, F, M, N, O, P y H es decir son las hojas del árbol.
El único nodo de grado 1 es J.
Los nodos de grado 2 son A, B, D y E.
Los nodos de grado 3 son C y G.
No existen nodos de mayor grado, por tanto, el grado del árbol es 3.
Los nodos de un árbol pueden dividirse en niveles; el nivel de un nodo esel número de nodos en el camino de él a la raíz. La altura de un árbol es el nivel máximo de todos los nodos en el árbol, es decir, la distancia máxima de la raíz a cualquier nodo.
Ejemplo:
A continuación se muestra el nivel de cada nodo del árbol de la figura anterior.
De lo anterior, se ve que el árbol es de altura 4.
A veces la forma en la cual los hijos de cada nodo están...
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 construye el á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ó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 como rama.
Los árboles son una de las estructuras de datos no lineales más utilizada. Sirve para representar estructuras de información jerárquicas y direcciones o etiquetas de una manera organizada.
Aplicaciones de los Árboles GeneralesPor ejemplo:
* organizar tablas de símbolos en compiladores
* representar tablas de decisión
* asignar bloques de memoria de tamaño variable
* ordenar
* buscar
* solucionar juegos
* probar teoremas
Los árboles permiten representar situaciones de la vida diaria como son:
* organización de una empresa
* árbol genealógico de una persona
*organización de torneos deportivos
Definición: Un árbol es un conjunto finito T de uno o más nodos tal que:
a) Existe un nodo especial llamado la raíz de árbol
b) Los nodos restantes están particionados en m > 0 conjuntos disjuntos T1,...,Tm y cada uno de estos conjuntos es a su vez un árbol. Los árboles T1,...,Tm son llamados subárboles de la raíz
Cualquier nodo es la raíz de unsubárbol que consiste de él y los nodos debajo de él. Esto se deriva de la definición recursiva de árbol presentada.
Un árbol puede representarse gráficamente de muchas formas. Algunas de ellas son por medio de:
* conjuntos anidados:
* paréntesis anidados.
(1(2(4(9,10, 11),5),3(6(12),7,8)))
* indentación
* grafos
La forma más común de representar a los árboleses por medio de un grafo con la raíz hacia arriba:
Cada vértice o nodo del árbol puede tener un nombre y puede tener una información asociada; un arco es una conexión entre dos vértices.
Un camino en un árbol es una lista de vértices diferentes en los que vértices sucesivos están conectados por arcos en el árbol. Una propiedad que define a los árboles es que existe exactamente un caminoentre la raíz y cada uno de los otros nodos en el árbol.
La longitud de un camino es el número de nodos del camino menos uno. Por tanto, hay un camino de longitud cero de cualquier nodo a si mismo.
Se dice que un nodo Y está abajo de un nodo X, si X está en el camino de Y a la raíz. Además, cada nodo, excepto la raíz, tiene exactamente un nodo arriba de él, que es llamado su padre; los nodosque están exactamente abajo de él son llamados sus hijos.
El número de hijos que cuelgan de un nodo es llamado el grado del nodo. El grado de un árbol es el grado máximo de los nodos del árbol. Un nodo de grado cero es llamado hoja, es decir, no tiene hijos.
Ejemplo:
Considere el siguiente árbol:
El camino del nodo A al nodo P es (A, B, D, J, P), cuya longitud de camino es 4. E esel padre de K y L.
Los hijos de G son M, N y O.
Los nodos de grado 0 son: I, P, K, L, F, M, N, O, P y H es decir son las hojas del árbol.
El único nodo de grado 1 es J.
Los nodos de grado 2 son A, B, D y E.
Los nodos de grado 3 son C y G.
No existen nodos de mayor grado, por tanto, el grado del árbol es 3.
Los nodos de un árbol pueden dividirse en niveles; el nivel de un nodo esel número de nodos en el camino de él a la raíz. La altura de un árbol es el nivel máximo de todos los nodos en el árbol, es decir, la distancia máxima de la raíz a cualquier nodo.
Ejemplo:
A continuación se muestra el nivel de cada nodo del árbol de la figura anterior.
De lo anterior, se ve que el árbol es de altura 4.
A veces la forma en la cual los hijos de cada nodo están...
Leer documento completo
Regístrate para leer el documento completo.