Estructura de arbol

Universidad Columbia del Paraguay
Ingeniería informática

TEMA: Estructura de Árbol

Algoritmia 2

Lic. Miguel Franco

Integrantes
Artemio Morales
Yessil Álvarez
Diego Sánchez
Sergio Canella
1º “T”

Asunción – Paraguay
2010

INDICE

Introducción………………………………………………………………… Pág.

Estructura de Arbol

INTRODUCCION
El siguiente trabajo trata sobre la estructura de datosno lineales llamada árbol. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos, y tablas de contenidos.
Con este trabajo se pretende incrementar el conocimiento acerca de las estructuras de datos dentro del lenguaje de programación, en este caso la estructura árboles, de la cual seha recolectado información  general y se ha incluido en este trabajo una abstracción de dicha información . Los arboles surgen en redes que se modelan mediante grafos, en una red de comunicaciones, por ejemplo, puedes ser necesario que toda pareja de nodos de la red esté conectada con el mínimo coste posible, y la solución de este problema implica la construcción de otra clase de árbol denominadaárbol de expansión.

Estructura de Árbol
Concepto
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 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 (enese 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.
Definición: Forma de estructurar cosas en una jerarquía gráfica. Es llamada "árbol" por que parece un árbol natural pero invertido.

Los árboles comienzan conun nodo-raíz principal, y se subdividen en hijos hasta al alcanzar las hojas (aquellos nodos que no tienen hijos). Los nodos hijos sólo tienen un padre.

Terminología, Nomenclatura Básicas
Terminología:
• Hijo: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.
• Padre: X es padre de Y sí y solo sí el nodo X apunta a Y.También se dice que X es antecesor de Y.
• Hermano: Dos nodos serán hermanos si son descendientes directos de un mismo nodo.
• Hoja: Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).
• Nodo anterior: Es un nodo que no es raíz ni terminal.
• Grado: Es el número de descendientes directos de un determinado nodo.
• Grado de un árbol: Es elmáximo grado de todos los nodos del árbol.
• Nivel: Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.
• Altura: Es el máximo número de niveles de todos los nodos del árbol.
• Peso: Es el número de nodos del árbol sin contar la raíz.
• Longitud de camino: Es el número de arcos que deben ser recorridos para llegardesde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.

Nomenclatura sobre arboles

- Raíz: es aquel elemento que no tiene antecesor; ejemplo: a.
- Rama: arista entre dos nodos.
- Antecesor: un nodo X es es antecesor de un nodo Y si por alguna de las ramas de X se puedellegar a Y.
- Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X.
- Grado de un nodo: el número de descendientes directos que tiene. Ejemplo: c tiene grado 2, d tiene grado 0, a tiene grado 2.
- Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d
- Nodo interno: aquel que tiene al menos un descendiente.
-...