Arboles Binarios

Se define un árbol binario como un conjunto finito de elementos (nodos) que bien está vacío o está formado por una raíz con dos árboles binarios disjuntos, es decir, dos descendientes directos llamados subárbol izquierdo y subárbol derecho.

Los árboles binarios (también llamados de grado 2) tienen una especial importancia.

Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.

Terminología

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

 Hijo: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.

 Padre: X es padre de Y sí y solo sí 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 le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).

 Nodo anterior: Es un nodo que no es raíz ni terminal.

 Grado: Es el número de descendientes directos de un determinado nodo.

 Grado de un árbol: 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 máximo número de niveles de todos los nodos del árbol.

 Peso: Es el número de nodos del árbol sin contar la raíz.

 Longitud de camino: Es el número 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.

DESARROLLO

ARBOLES BINARIOS:

Las listas ligadas por lo general proporcionan mayor flexibilidad que los arreglos, pero son estructuras lineales y es difícil utilizarlas para representar una organización jerárquica de los objetos, aun cuando las pilas y colas reflejan ciertas jerarquías, están limitadas a una sola dimensión. Para superar esta limitación, creamos un tipo de datos nuevos llamado árbol que se compone de nodos y arcos a diferencia de los arboles naturales estos árboles se representan de arriba abajo con la raíz en la parte superior las hojas (nodos terminales) en la parte inferior. La raíz es un nodo que no tiene padre; solo puede tener nodos hijos las hojas por otro lado, no tienen hijos, o en vez de ello sus hijos son nulos. Un árbol puede definirse de manera recursiva como sigue:

1. Una estructura vacía es un árbol vacío.

2. Si t1…., tk son arboles disjuntos, entonces la estructura cuya raíz tiene como sus hijos a las raíces de t1…., tk también es un árbol.

3. Solo las estructuras generadas por las reglas 1 y 2 son árboles.

Cada nodo debe ser alcanzable desde la raíz hasta una secuencia única de arcos llamada camino. El número de arcos en un camino se llama longitud de camino. El nivel de un nodo es la longitud del camino desde la raíz al nodo más 1 que es el número de nodos en el camino. La altura del árbol no vacío es el nivel máximo de un nodo en el árbol. El árbol vacío es un árbol legítimo de altura cero (por definición), y un nodo individual es un árbol de altura 1 este es el único caso en el cual un nodo es tanto la raíz como la hoja. El nivel de un nodo debe de estar entre 1 (el nivel de la raíz) y la altura del árbol, lo cual paso en caso extremo es el nivel de la única hoja de un árbol degenerado asemejándose a una lista ligada.

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene 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.

Definición de teoría de grafos

Un árbol binario sencillo de tamaño 9, 4 niveles y altura 3 (altura = máximo nivel - 1), con un nodo raíz cuyo valor es 2.

En teoría de grafos, se usa la siguiente definición: Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a De esta forma sólo existe un camino entre un par de nodos.

Un árbol binario con 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 rehusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque.

Tipos de árboles binarios

Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.

Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.

Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).

A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Los nodos se clasifican dependiendo de su posición dentro del árbol en:

 Raíz: Elemento mínimo de un árbol.

 Nodo intermedio: Cualquier nodo predecesor de una hoja, y sucesor de la raíz.

 Nodo terminal u hoja: Nodo que no tiene sucesores.

También los podemos dividir en:

 Nodo interno: Cualquier nodo del árbol.

 Nodo externo: Son los árboles vacíos que penden de los nodos que no tienen todos sus hijos, (en los árboles de orden N). Se representa por G.

Conceptos más importantes son:

 Padre: Predecesor máximo de un nodo.

 Hijo: Cualquiera de los sucesores directos de un nodo

 Hermano: Cualquier otro nodo hijo de un mismo padre.

ESTRUCTURA DE ARBOLES BINARIOS:

Un árbol binario sencillo de tamaño 9, 4 niveles y altura 3 (altura = máximo nivel - 1), con un nodo raíz cuyo valor es 2.

...