ARBOLES BINARIOS.

1.  ARBOLES BINARIOS

Definición:  Es una Estructura de Datos de tipo dinámico que vincula nodos de forma jerárquica del mismo tipo.

1.1  CONCEPTOS BASICOS

• NODO RAIZ PRINCIPAL:  Es el nodo inicial en un árbol y posee una estructura como la siguiente:

[pic 1]

[pic 2][pic 3][pic 4][pic 5][pic 6][pic 7][pic 8][pic 9][pic 10][pic 11][pic 12][pic 13][pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20][pic 21][pic 22]

[pic 23]

[pic 24]

[pic 25]

[pic 26]

Teniendo en cuenta el árbol anterior se definen cada uno de los siguientes términos:

• NODO HOJA:  Un nodo es hoja cuando no posee nodos hijos por las dos ramas. Ej: 10,40,65,180
• NODO DESCENDIENTE: Un nodo es descendiente cuando posee en la ramificación del árbol un nodo ancestro. Ej:  (30,60,120 y 160 son descendientes de 100), (10,40 y 65 son descendientes de 50) y 180 es descendiente de 150.
• NODO ANCESTRO: Un nodo es ancestro cuando posee en la ramificación del árbol nodos descendientes.  Ej: 100 es ancestro de 30,60,120 y 160; 50 es ancestro de 10,40 y 65.
• NODO HERMANO: Dos nodos son hermanos si son hijos de un mismo nodo raíz o padre.  Ej:  30 y 60 son hermanos; 120 y 160 son hermanos; etc,...
• PESO:  El peso se analiza sobre un nodo especifico; es el número de nodos que dependen de él sin contarse este. Ej:  Peso(50)=5; Peso(100)= 10
• GRADO:  El grado de un nodo en un árbol binario fluctua entre 0 ó 2 (número máximo de hijos que pueden enlazarse a un nodo. Ej:  Grado (160)= 1, Grado (100)= 2, Grado(120)=0
• NIVEL:  El nivel de un árbol lo determina la posición (N-1) en las ramas del o los nodos hoja más distantes de la raíz principal del árbol.  Ej:  Nivel (N-1)=(4-1)=3
• ALTURA: La altura de un árbol la determina el nivel del árbol.
• ARBOLES BINARIOS IGUALES:  Dos arboles binarios son iguales cuando conservan la misma estructura y el mismo contenido.

[pic 27][pic 28]

                        ARBOL  1                          ARBOL  2

• ARBOLES BINARIOS SEMEJANTES: Dos árboles binarios son iguales cuando conservan el mismo contenido, aunque la estructura del árbol sea diferente.

[pic 29]

[pic 30][pic 31][pic 32][pic 33][pic 34]

[pic 35][pic 36]

[pic 37]

[pic 38]

ARBOL  1                          ARBOL  2

• ARBOLES BINARIOS ISOMORFOS:  Dos árboles binarios son isomorfos si tienen la misma estructura, aunque el contenido de cada uno de sus nodos sea diferente.

[pic 39]

           ARBOL  1                                ARBOL  2

1.2  CREACION Y ORDENAMIENTO ASCENDENTE DE UN ARBOL BINARIO

Para crear un árbol binario ordenado iniciamos con cualquier dato en el nodo raíz principal;  posteriormente se evalúa si el siguiente dato que ingresa es mayor o menor que el dato que se encuentra en el nodo raíz principal; si es mayor se inserta por derecha, si es menor se inserta por izquierda, si ya se encuentra insertado, no se debe volver a insertar.

...