Los arboles binario tiene como característica primaria que TODOS LOS NODOS TIENE COMO MÁXIMO 2 HIJOS.
Y la gran diferencia entre el árbol binario común y el de búsqueda es que el segundo esta optimizado para las búsquedas, por lo tanto, encontrar un nodo sera mucho mas rápido y fácil que en el árbol binario común.
Llevándolo a java la clase NodoBinario seria algo así (nuevamente asumamos que almacenaremos int para facilitar la idea):
Tal cual como en el árbol general, tendremos 2 clases. Una clase sera el ArbolBinario y la segunda (que perfectamente podría heredar de la primera o ambas heredar de un Binario General para reusar los atributos) ArbolBinarioBusqueda
Explicaciones rápidas sobre cada uno
Árbol Binario de Búsqueda (De este árbol no hay muchas variantes)
Este árbol tiene la característica que alacena los nodos con datos menores a la raíz a su izquierda mientras que los mayores a él en su derecha (en algunos casos cuando el dato es el mismo simplemente se ignora para no tener repetidos o reemplazarlo).
Por lo tanto un árbol valido podría ser el siguiente
4
3 5
Donde, como el 3 es menor que el 4, entonces debe ser almacenado a la izquierda del 4. El 5 es mayor que el 4 por lo tanto debe ser almacenado a la derecha del 4.
En caso de un árbol con muchos nodos, el algoritmo de inserción o búsqueda, deberá ir evaluando si el dato del nodo actual es mayor o menor al dato dado, para saber si continua su camino por el hijo izquierdo o derecho del nodo actual hasta que encuentre el dato o llegue hasta un nodo en null (osea que el dato no se encontró).
Árbol binario
De este Árbol puedes encontrar una cantidad bastante mayor de implementaciones dependiendo de las necesidades.
La mayor diferencia, a mi parecer, es la forma en la que se insertan los nodos, dado que podrías llegar a tener 3 variantes:
* La primera variante es indicar en el método de insertar el dato a insertar, el padre que tendrá y que hijo sera (si el derecho o izquierdo), esta no es la implementan mas popular pero se puede ver
* La segunda variante es indicar al método de insertar el dato a insertar y el padre del mismo, dejando al algoritmo decidir si lo inserta en el hijo izquierdo o derecho dependiendo de cual tenga libre
* La tercer variante y mas compleja, es indicar solo el dato a ingresar y permitir que el algoritmo de inserción vaya insertando nodos de tal forma que asegure que antes de comenzar a insertar en un nuevo nivel, haya completado los hijos de todos los nodos del nivel superior. Si tomamos el árbol binario anterior como ejemplo, hasta que el nodo 3 y 5 no tengan sus respectivos hijos no insertara un hijo a los "nietos" digamos.
Ejemplo de la tercera variante con números.
Si quisiéramos ingresar el 1, este seria hijo del 3 o del 5 dependiendo de como se implemente el algoritmo(asumamos que completamos primero el 3 y luego el 5).
Por lo tanto el hijo izquierdo del 3 sera el 1.
Luego intentamos insertar los datos 0, 6 , 7 y 8. Entonces el algoritmo asignara el 0 al hijo derecho del 3, el 6 al hijo izquierdo del 5, el 7 al hijo derecho del 5 y el 8 al Hijo izquierdo del 1 (nunca va asignar hijos al 1 sin terminar de asignarle hijos al 5).
Creo que con esto tienes bastante para empezar. A medida que vayas avanzando podemos ir profundizando en los algoritmos y las dudas que hayan.
Espero que sirva la explicación
