Arboles Binarios (Matemáticas Discretas)

Instituto tecnologico superior de fresnillo
Ing.Sistemas computacionales
Matematicas discretas
Unidad 6
Neftali Gpe Segovia Rodriguez.
Lizbeth Monreal Ruiz.

Arboles Binarios:

Un árbol binario es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. 

No pueden tener más de dos hijos (de ahí el nombre "binario").

Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno.

Características de los árboles

Recorridos de Árboles

·        Hijo: Es aquel nodo que siempre va a tener un nodo antecesor o padre, son  aquellos que se encuentran en el mismo nivel

·        Padre: Es aquel que tiene hijos y también puede tener o no antecesores.

·        Hermano: Dos nodos son hermanos si son apuntados por el mismo nodo, es         decir si    tienen el mismo padre.

·        Raíz: Es el nodo principal de un árbol y no tiene antecesores.

·        Hoja o terminal: Son aquellos nodos que no tienen hijos o también los nodos         finales de un árbol.

·        Interior: Se dice que un nodo es interior si no es raíz ni hoja.

·        Nivel de un nodo: Se dice que el nivel de un nodo es el numero de arcos que       deben ser recorridos, partiendo de la raíz para llegar hasta el.

·        Altura del árbol: Se dice que la altura de un árbol es el máximo de los niveles       considerando todos sus nodos.

·        Grado de un nodo: se dice que el grado de un nodo es el número de hijos             que  tiene dicho nodo.

        Para que sirve un árbol binario?

        Como todos sabemos un árbol binario es una estructura de datos, y como todas, este sirve para organizar datos para facilitar su manipulación, ya sea el ingreso, borrado o búsqueda de datos, y precisamente una de las principales ventajas de los árboles binarios es la búsqueda, ya que como

    en muchos algoritmos de búsqueda necesitamos tener la información ordenada .

Árbol binario lleno

Es aquel árbol en el que los nodos de cada nivel tienen sus dos hijos o ninguno 

Árbol binario completo

Es aquel árbol binario lleno en que todas sus hojas están en el nivel n o n-1 considerando que para un hijo derecho hay siempre un hijo izquierdo. Estos árboles ocupan todas las posiciones del vector. Por lo tanto, todo árbol binario lleno es completo, pero no la viceversa.

Árboles de expresión

Son árboles binarios que se utilizan para almacenar en la memoria de una computadora expresiones lógicas, aritméticas o algebraicas. Este proceso lo realizan los compiladores de los lenguajes de programación. 

Árbol binario de búsqueda

Un árbol binario de búsqueda es aquel que tiene sus nodos con un orden definido, de tal manera que los datos del subárbol izquierdo son menores y los del subárbol derecho son mayores. Estos árboles tienen como particularidad la permisión de que se puedan realizar búsquedas de nodos o datos determinados, utilizando el método de búsqueda binaria de manera similar al usado en arreglos. 

Un recorrido en un árbol binario es Una operación que consiste en visitar todos sus vértices o nodos, de tal manera que cada vértice se visite una sola vez. 

Se distinguen tres tipos de recorrido: INORDEN, POSORDEN Y PREORDEN. 

En cada recorrido se tiene en cuenta la posición de la raíz (de ahí su nombre) y que siempre se debe ejecutar primero el hijo izquierdo y luego el derecho.

Recorrido INORDEN. Este recorrido se realiza así: primero recorre el subárbol izquierdo, segundo visita la raíz y por último, va al subárbol derecho. En síntesis: 

hijo izquierdo — raíz — hijo derecho.

Recorrido PREORDEN. Este recorrido se realiza así: primero visita la raíz; segundo recorre el subárbol izquierdo y por último va a subárbol derecho. En síntesis: 

raíz — hijo izquierdo — hijo derecho.

Recorrido POSORDEN. Primero recorre el subárbol izquierdo; segundo, recorre el subárbol derecho y por último, visita la raíz. En síntesis: 

hijo izquierdo– hijo derecho — raíz 

Arboles binarios en java

Como pueden ver aquí tenemos el nodo raíz  que tiene como valor 1.

A los nodos se les pone nodo 2, 3,4 etc. porque pueden ser varios nodos los que pueden existir, esto con la intención de no confundirnos .También está el sub árbol izquierdo que tiene como valor 2.Y el sub árbol derecho que tiene como valor 3.

En esta imagen el subárbol derecho en donde este árbol va a tener dos hijos el cual a uno de sus hijos se le asigna un valor de 6 y al otro hijo un valor de 5. Y también está el subárbol izquierdo, que en esta ocasión solo se le asignara un hijo con un valor de 4.

 

Por ultimo tenemos la raíz, que en este apartado solamente nos dice  que la raíz tiene dos nodos o subárboles el nodo2 que es el izquierdo y el nodo 3 que es el derecho.

Después se hacen métodos  uno para el nodo, otro para el nodo izquierdo y para el nodo derecho, en donde en el método del dato va a hacer que este dato sea igual al dato de entrada. En el método de nodo izquierdo nos va a dar como resultado que es izquierdo. Y en el método derecho nos va a dar solamente como resultado si el nodo es derecho

El método de set nodo derecho e izquierdo es para agrega un nuevo nodo, por ejemplo si tengo un nodo denominado raíz puedo agregarle  un nodo  hijo

Tipos de recorrido en java

En este apartado se hace un método para el recorrido preorden el cual es de la siguiente manera primero lee la raíz es por eso que en el system se pone raíz.getdato

Después lee el nodo izquierdo el cual se pone getNodoizquierdo

Y por último el nodo derecho

En este apartado se hace un método para el recorrido posorden el cual es de la siguiente manera primero lee el nodo izquierdo, después el nodo derecho y por último la raíz.

En este apartado se hace un método para el recorrido posorden el cual es de la siguiente manera primero lee el nodo izquierdo, después lee la raíz y por último el nodo derecho.

Como pueden ver en esta imagen están los resultados de los tres tipos de recorrido y los tres son correctos.