arboles :programacion 1

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Educación Superior
Universidad Nacional Experimental de la Fuerza Armada Bolivariana
(UNEFA)
Ing. Sistemas Sección “A”
Cátedra: Lenguaje de Programación










Prof: Sonaly Gutiérrez Realizado Por:
Jessica Romero
C.i:21155235
Sección: “A” Nocturno


Comunidad Cardón, Enero de 2013
Un árbol esuna 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.
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  ycada una de las raíces de los  árboles. El árbol resultante de  nodos tiene como raíz el nodo, los nodos  son los hijos de  y el conjunto de nodos hoja está formado por la unión de los  conjuntos hojas iníciales. 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 deparentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero 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 losnodos 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:
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 cobrasignificado en los árboles binarios) consiste en recorrer en primer lugar , luego la raíz y luego cada uno de los hijos  en orden 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 conceptode árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico.

Arboles Binarios: Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijoes llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

Un árbol binario puede declararse de varias maneras. Algunas de ellas son:
Estructura con manejo de memoria dinámica, siendo punta el puntero que apunta al árbol de tipo tArbol:
typedef struct nodo {
int clave;
struct nodo *izdo,*dcho;
}Nodo;
Estructura con arreglo indexado:
typedef struct tArbol
{
int clave;
tArbol hIzquierdo, hDerecho;
} tArbol;
tArbol árbol[NUMERO_DE_NODOS];

En el caso de un árbol binario casi-completo (o un árbol completo), puede utilizarse un sencillo arreglo de enteros con tantas posiciones como nodos deba tener el árbol. La información de la ubicación del nodo en el árbol es...