Árboles binarios

Los arboles binarios son arboles de grado u orden 2, es decir, cada nodo puede tener como mucho dos hijos.

Tipos de árboles binarios

Full Binary Trees

• Full Binary Trees: Todos los nodos del árbol binario tienen o ningún hijo o sus dos hijos

Complete Binary Trees

• Complete Binary Trees: El ultimo nivel de un full binary tree puede permitirse prescindir de alguno de sus hijos, es decir, por ejemplo tener solamente un hijo, con la condición de que el nodo hoja sea el hijo de la izquierda

En el mundo de los arboles binarios los tipos se pueden solapar, es decir, podemos llegar a cuatro tipos de arboles binarios:

• Full Binary Tree
• Complete Binary Tree
• Full and Complete
• Neither Full Nor Complete (ni complete ni full)

Arbol degenerados

Hay otro tipo especial de árbol, los llamados arboles degenerados, en los que cada nodo solo tiene un hijo, se comportan como listas enlazadas

Árboles balanceados

Un árbol binario balanceado intenta mantener la profundidad de sus dos subárboles la menor posible.

El balanceo o equilibrio de un árbol hace que algunas operaciones sean más eficientes.(búsquedas)

Algunos árboles especiales se aprovechan del balanceo. Dependiendo de qué tipo de balanceo intentemos usar se usa una regla u otra distinta para balancear. (Ej: Arboles avl)

Estructura en código

Cuando tenemos un árbol binario la estructura puede cambiar.

Ejemplo

class Node_BT{
	private int value;
	
	private Node_BT left;
	
	private Node_BT right;
}

Operaciones con árbol binario

Recorridos

Se muestra unas pinceladas de como recorrer un árbol binario, pero se verá más en profundidad más adelante

Existen varías formas de recorrer un árbol:

• En anchura
• En profundidad
  • En preorden
  • En inorden
  • En postorden

Recorrido en anchura

Consiste en procesar a la vez todos los elementos del mismo nivel.

Cuando hemos terminado con un nivel pasamos al siguiente.

Comenzamos recorriendo [16], pasamos al siguiente nivel y recorremos [8, 24], en el siguiente, [3, 13, 19] y por último, [7, 21]. Se suele realizar con colas(queues), se verá más adelante

Recorrido en profundidad

Es mejor considerar los nodos izquierdo y derecho como subárboles. En un recorrido en profundidad se van a procesar:

• La raíz
• El subárbol izquierdo
• El subárbol derecho

Dependiendo del tipo de recorrido, tenemos varias configuraciones

Preorden

• Procesamos la raíz
• Procesamos el árbol izquierdo
• Procesamos el árbol derecho

Inorden

• Procesamos el árbol izquierdo
• Procesamos la raíz
• Procesamos el árbol derecho

Postorden

• Procesamos el árbol izquierdo
• Procesamos el árbol derecho
• Procesamos la raíz

Preorder = procesa el valor del nodo actual, procesa el valor de los nodos de la izquierda, procesa los nodos de la derecha

Inorden = procesa el valor del nodo de la izquierda, procesa los nodos a los que acccediste, procesa los nodos de la derecha

Postorden = procesa el los nodos de la izquierda, procesa los nodos de la derecha y procesa el valor del nodo actual.

Preorden = 8,6,4,3,5,7,12,11,13,14

Inorden = 3,4,5,6,7,8,11,12,13,14

postorden = 3,5,4,7,6,11,14,13,12,8

         8          
                    
                    12
	   6       
	  
	       7           11     13
	 4                    
	                             14

3	      5