2.2 Árboles de búsqueda

Un árbol es un tipo de estructura jerarquizada alternativo a las listas enlazadas, y son utilizados en la programación de hojas de cálculo y en inteligencia artificial. Es una forma particular de grafo dirigido.
 
Las estructuras tipo árbol se usan principalmente para representar datos con una relación jerárquica entre sus elementos, como arboles genealógicos, tablas, etc.

Elementos de una estructura de árbol

• Nodo: Se denomina nodo a cada elemento de la estructura. Cada nodo de ramifica con otros siguiendo algún criterio.
• Raíz: Es el elemento superior del árbol.
• Hojas o terminales: Son los nodos que no tienen subárboles.
• Nivel o profundidad: Es el largo del camino de la raíz al nodo. Cada vez que un nodo se ramifica aumenta el nivel.

• Altura: Son las capas que crecen a partir de la raíz. La altura de un árbol es la altura de la raíz.
• Grado: Es el número de descendientes directos de un nodo. El grado máximo de todos los nodos es el grado del árbol.

 Arboles Binarios 

Los árboles binarios son los que tienen a lo más dos hijos por cada nodo.

Clasificación de Arboles Binarios

Existen cuatro tipos de árbol binario:

• Árbol Binario Distinto: Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.

• Árbol Binario Similar: Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.

• Árbol Binario Equivalente: Son aquellos arboles que son similares y que además los nodos contienen la misma información.

• Árbol Binario Completo: 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.

Recorridos para un árbol binario 

IN-ORDEN (IRD). Consiste en recorrer el árbol en el orden en que está.

POST-ORDEN (IDR). Consiste en recorrer las ramas en orden inverso.

PRE-ORDEN (RID). Consiste en recorrer las ramas desde la raíz hacia abajo.

Árboles De Búsqueda Binaria 

Un Árbol de Búsqueda Binaria es un árbol binario en el cual se ingresan siempre los menores elementos a la izquierda.