Arboles Binarios

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Educación.
Instituto Universitario de Tecnología Antonio José de Sucre.
Valencia Edo. Carabobo – 05/05/2013.









Nombre: Randy M. Marrufo C.
C.I.:20.179.320
Cod.:78

Definición de teoría de grafos:
La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias dela Computación. Los grafos constituyen una herramienta básica para modelar fenómenos discretos y son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos.

En matemáticas y ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados vértices (o
nodos) conectados por líneasllamadas aristas (o arcos) que pueden tener orientación (dirección asignada). Típicamente, un grafo está diseñado por una serie de puntos (los vértices) conectados por líneas (las aristas).

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de
Königsberg es considerado como uno de los primeros resultados de la teoría de
grafos. También se considera uno delos primeros resultados topológicos en
geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda
relación entre la teoría de grafos y la topología.

En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el
voltaje y la corriente en los circuitos eléctricos. En 1852 Francis Guthrie planteó el problema de los cuatro colores que planteasi es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricosfundamentales de los grafos.




Tipos de Arboles Binarios:
Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, tambiénllamada altura).
A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.


Clasificación de arboles binarios:

Existen cuatro tipos de árbol binario:.
A. B. Distinto.
A. B. Similares.
A. B. Equivalentes.
A. B. Completos.
A continuación sehará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos.
A. B. DISTINTO
Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes. Ejemplo:


A. B. SIMILARES
Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente. Ejemplo:

A. B.EQUIVALENTES
Son aquellos arboles que son similares y que además los nodos contienen la misma información. Ejemplo:

A. B. COMPLETOS
Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.


Terminología de Árboles Binarios:
1. * NODO indica un elemento, o ítem, de información.

2. * Todo árbolque no es vacío, tiene un único nodo raíz.

3. * Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. X es hijo de Y.

4. * Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. X es padre de Y.

5. *Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.

6. * Todo nodo que no...