Un árbol es una estructura jerárquica de datos que imita la forma de u árbol (un conjunto de nodos conectados).

Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o mas nodos hijos conectados a el. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b. (en ese caso también decimos que b es hijo de a). Solo puede haber un único hijo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre o uno o mas hijos) se les conoce como rama.

TIPOS DE ÁRBOLES

o Árboles binarios

o Árbol de búsqueda

binarios auto-balanceable

· Árboles rojo-negro

· Árboles AVL

o Árboles B

· Árbol _B+

· Árbol _B*

o Árboles multicamino

TERMINOLOGIA

La terminología que por lo general se utiliza para el manejo de árboles es la siguiente:

HIJO: X es hijo de Y, si y solo si el nodo X es apuntado por Y. también se dice que X es descendiente directo de Y.

PADRE: X es padre de Y, si y solo si 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 les llama hoja o Terminal a aquellos nodos que no tienen ramificaciones (hijos).

NODO INTERIOR: Es un nodo que no es raíz ni Terminal.

GRADO: Es el numero de descendientes directos de un nodo determinado.

GRADO DEL ARBOL: es el má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 número máximo de niveles de todos los nodos del árbol.

PESO: Es el numero de nodos del árbol sin contar la raíz.

LONGITUD DE CAMINO: Es el numero de arcos que deben ser recorridos para llegar desde 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.

ÁRBOLES BINARIOS

En teoría de grafos, “un árbol binario es un grafo conexo, aciclico y no dirigido tal que el grado de cada vértice no es mayor a 3”. De esta forma solo existe un camino entre un par de nodos. Un árbol binario es una estructura de datos en la cual cada nodo:

o No tiene hijos o Tiene un hijo izquierdo y uno derecho

o Tiene un hijo izquierdo

o Tiene un hijo derecho Un árbol binario enraizado es como un grafo que tiene uno de sus vértices llamado raíz, de grado no mayor a 2.

Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si reusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta ultima estructura un bosque.

CLASIFICACION DE LOS ARBOLES BINARIOS

Existen cuatro tipos:

ü A.B DISTINTO: Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.
ü A.B SIMILARES: dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos son diferentes.
ü A.B EQUIVALENTES: son aquellos arboles que son similares y que a demás los nodos contienen la misma información.
ü A.B COMPLEJOS: son aquellos en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho. RECORRIDO DE UN ARBOL BINARIO

Hay tres maneras de recorrer un árbol:

INORDEN:

-Recorrer el subárbol izquierdo en inorden.

-Examinar La raíz.

-Recorrer el subárbol derecho en inorden.

PREORDEN:

-Examinar la raíz.

-Recorrer el subárbol izquierdo en preorden.

-Recorrer el subárbol derecho en preorden.

POSTORDEN:

-Recorrer el subárbol izquierdo en postorden.

-Recorrer el subárbol derecho en postorden.

-Examinar la raíz.

CARACTERISTICAS DE LOS ARBOLES BINARIOS

*Cada nodo puede tener como máximo 2 subárboles.

*Cada subárbol se identifica como el subárbol izquierdo o el subárbol derecho de su padre.

*Puede ser vació.