Árbol binario

De Wikipedia, la enciclopedia libre

Para otros usos de este término, véase Árbol binario (desambiguación).

En ciencias de la computación, un árbol binario es una estructura de datos en el cual cada nodo tiene como máximo dos nodos hijos. Típicamente los nodos hijos son llamados izquierdo y derecho. Usos comunes de los árboles binarios son los árboles binarios de búsqueda y los montículos binarios.

[editar] Definición de teoría de grafos

Un árbol binario sencillo de tamaño 9 y altura 3, 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 3». 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 reusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque.

[editar] 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 casi-completo es un árbol en el que cada nodo que tiene un hijo derecho también tiene un hijo izquierdo. Tener un hijo izquierdo no requiere que un nodo tenga un hijo derecho. Dicho de otra forma, un árbol casi completo es un árbol donde para un hijo derecho, hay siempre un hijo izquierdo, pero para un hijo izquierdo puede no haber un hijo derecho.

[editar] Implementación en C

Un árbol binario puede declararse de varias maneras. Algunas de ellas son:

Estructura con manejo de memoria dinámica:

typedef struct tArbol
{
  int clave;
  struct tArbol *hIzquierdo, *hDerecho;
} tArbol;

Estructura con arreglo indexado:

typedef struct tArbol
{
  int clave;
  int hIzquierdo, hDerecho;
};
tArbol arbol[NUMERO_DE_NODOS];

En el caso de un árbol binario casi-completo (o un árbol completo), puede utilizarse un sencillo arreglo de enteros con tantas posiciones como nodos deba tener el árbol. La información de la ubicación del nodo en el árbol es implícita a cada posición del arreglo. Así, si un nodo está en la posición i, sus hijos se encuentran en las posiciones 2i+1 y 2i+2, mientras que su padre (si tiene), se encuentra en la posición truncamiento((i-1)/2) (suponiendo que la raíz está en la posición cero). Este método se beneficia de un almacenamiento más compacto y una mejor localidad de referencia, particularmente durante un recorrido en preorden. La estructura para este caso sería por tanto:

int arbol[NUMERO_DE_NODOS];

[editar] Recorridos sobre árboles binarios

[editar] Recorridos en profundidad

[editar] Recorrido en preorden

En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.

void preorden(tArbol *a)
{
  if (a != NULL) {
    tratar(a);                        //Realiza una operación en nodo
    preorden(a->hIzquierdo);
    preorden(a->hDerecho);
  }
}

[editar] Recorrido en postorden

En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.

void postorden(tArbol *a)
{
  if (a != NULL) {
    postorden(a->hIzquierdo);
    postorden(a->hDerecho);
    tratar(a);                        //Realiza una operación en nodo
  }
}

[editar] Recorrido en inorden

En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4 y 9.

Pseudocódigo:

funcion inorden(nodo)
inicio
    si(existe(nodo))
        inicio
            inorden(hijo_izquierdo(nodo));
            visitar(nodo);                     //Realiza una operación en nodo
            inorden(hijo_derecho(nodo));
        fin;
fin;

Implementación en C:

void inorden(tArbol *a)
{
  if (a != NULL) {
    inorden(a->hIzquierdo);
    tratar(a);                                 //Realiza una operación en nodo
    inorden(a->hDerecho);
  }
}

[editar] Recorridos en amplitud (o por niveles)

En este caso el recorrido se realiza en orden por los distintos niveles del árbol. Así, se comenzaría tratando el nivel 1, que sólo contiene el nodo raíz, seguidamente el nivel 2, el 3 y así sucesivamente. En el árbol de la figura el recorrido en amplitud sería: 2, 7, 5, 2, 6, 9, 5, 11 y 4.

Al contrario que en los métodos de recorrido en profundidad, el recorrido por niveles no es de naturaleza recursiva. Por ello, se debe utilizar una cola para recordar los subárboles izquierdos y derecho de cada nodo.

Pseudocódigo:

    encolar(raiz);
    mientras(cola_no_vacia())
        inicio
            nodo=desencolar();            //Saca un nodo de la cola
            visitar(nodo);                //Realiza una operación en nodo
            encolar_nodos_hijos(nodo);    //Mete en la cola los hijos del nodo actual
        fin;

Implementación en C:

void amplitud(tArbol *a)
{
  tCola cola;
  tArbol *aux;
  
  if (a != NULL) {
    crearCola(cola);
    encolar(cola, a);
    while (!colavacia(cola)) {
      desencolar(cola, aux);
      visitar(aux);                                                   //Realiza una operación en nodo
      if (aux->hIzquierdo != NULL) encolar(cola, aux->hIzquierdo );
      if (aux->hDerecho!= NULL) encolar(cola, aux->hDerecho);
    }
  }
}

[editar] Métodos para almacenar árboles binarios

Los árboles binarios pueden ser construidos desde lenguajes de programación primitivos en muchas formas. En un lenguaje con estructuras y referencias, los árboles binarios son típicamente implementados construyendo con una estructura de tres nodos que contiene algunos datos y referencias a su hijo izquierdo y a su hijo derecho.

[editar] Véase también

• Árbol (estructura de datos)
• Árbol multirrama
• Árbol binario de búsqueda
• Partición de espacio binario