ARBOLES



INDICE
Pág.
INTRODUCCION……………………………………………………………………….3
DESARROLLO………………………………………………………………………….4
ÁRBOLES, DEFICIONES………………………………………………………4
PROPIEDADES……………………………………………………..………...5-6
CARACTERISTICAS…………………………………………………………...6
TIPOS DE ÁRBOLES……………………………………………………….7-12
ÁRBOL EN EXPANSION………………………………………….…7-8
ÁRBOL DE EXPASION MINIMO……………………………………..8
ARBOLESBINARIOS…………………………………………….…….9
ARBOLES 2-3-4……………………………………………………..9-10
ARBOLES 2-3……………………………………………………....10-11
ARBOLES ROJO-NEGRO………………………………………....11-12
RECORRIDO DE ÁRBOLES……………………………………………...12-15
ISOMORFISMO DE UN ARBOL………………………………………….….15
PROGRAMAS DE ÁRBOLES……………………………………………..16-21
CONCLUSION……………………………………………..…………….……………22
BIBLIOGRAFIA…………………………………………………...…….…………….23
INTRODUCCION
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 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, quellamaremos 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.
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 recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad yprimero 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 son preorden,postorden e inorden. 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.



Árboles, definición:
El concepto general de árbol implica una estructura en la que los datos se organizan de modo que los elementos de información están relacionados entre sí a través de ramas. El árbol genealógico es elejemplo típico más representativo del concepto de árbol general.
Definición 1: un árbol es un grafo no dirigido conexo sin ciclos. Un bosque es un grafo no dirigido sin ciclos pero no conexo. Una definición equivalente es que un bosque es una unión disjunta de árboles (de aquí el nombre). Un árbol sueles recibir el nombre de árbol libre.

Figura 1. Ejemplos de grafo, árbol, bosque, nótese que elÁrbol no presenta ciclos
Definición 2 un árbol consta de un conjunto finito de elementos, llamados nodos y un conjunto finito de líneas dirigidas llamadas ramas que conectan los nodos.
Definición 3: Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.

Figura 2. Árbol con nodos y ramas
Demostración: Sea G un árbol. Como, por definición, G es conexo,entonces existe un camino elemental entre todo par de vértices de G. Ahora bien, este camino es único: si u y v son dos vértices cualesquiera de G y suponemos que existen dos caminos distintos de u a v, al unir dichos caminos se formaría un subgrafo de G que contendría un ciclo, debido a que existen dos caminos diferentes, hecho que nos lleva a una contradicción. Recíprocamente, si todo par devértices de G está a unido por un solo camino elemental.
Obviamente G es un grafo conexo y, además, G no contiene ciclos porque si existiera un ciclo todos los pares de vértices en él se podrían unir con dos caminos distintos.

Figura 3. Diferentes ejemplos de árboles.
Definiciones Complementarias
-Un nodo es hoja si no es padre de ningún nodo (vértice de grado 1).
-Un...