Ensamblador

Enviado por Programa Chuletas y clasificado en Otras materias

Escrito el en español con un tamaño de 7,48 KB

     

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.

También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

    • 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.

Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos.

En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo.

Árbol AVL es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.

En árboles de orden N se define:

Árbol lleno: es un árbol con todos sus niveles llenos. También podemos definirlo como el árbol

en el que la longitud del camino más largo y la del más corto desde cualquier nodo, son iguales.

Árbol Completo es un árbol con todos sus niveles llenos salvo quizás el último, que deberá estar completo, (sin "huecos") de izquierda a derecha.

Árbol perfectamente balanceado: Es aquél en el que el número de nodos de cada subárbol de cada nodo interno, no varía en más de uno. La palabra equilibrado suele emplearse como sinónimo de balanceado.

Árbol balanceado en altura como el árbol cuyos subárboles tienen alturas que difieren a lo más en una unidad y también son equilibrados en altura.



Árbol degenerado: Es aquél en el que cada nodo sólo tiene un subárbol. Equivale a una lista.

Desventajas (las típicas de una implementación dinámica):

- La memoria necesaria se toma en tiempo de ejecución.

- Todos los accesos a la información deben hacerse de forma indirecta.

- Recorridos en profundidad:

* Recorrido en preorden: consiste en visitar el nodo actual (visitar puede ser simplemente mostrar la clave del nodo por pantalla), y después visitar el subárbol izquierdo y una vez visitado, visitar el subárbol derecho. Es un proceso recursivo por naturaleza.
Si se hace el recorrido en preorden del árbol de la figura 1 las visitas serían en el orden siguiente: a,b,d,c,e,f.

void preorden(tarbol *a)
{
  if (a != NULL) {
    visitar(a);
    preorden(a->izq);
    preorden(a->der);
  }
}
* Recorrido en inorden u orden central: se visita el subárbol izquierdo, el nodo actual, y después se visita el subárbol derecho. En el ejemplo de la figura 1 las visitas serían en este orden: b,d,a,e,c,f.
void inorden(tarbol *a)
{
  if (a != NULL) {
    inorden(a->izq);
    visitar(a);
    inorden(a->der);
  }
}

* Recorrido en postorden: se visitan primero el subárbol izquierdo, después el subárbol derecho, y por último el nodo actual. En el ejemplo de la figura 1 el recorrido quedaría así: d,b,e,f,c,a.

void postorden(arbol *a)
{
  if (a != NULL) {
    postorden(a->izq);
    postorden(a->der);
    visitar(a);
  }
}

Entradas relacionadas: