Estructuras de Datos Dinámicas: Listas, Pilas, Colas y Árboles Binarios

Estructuras de Datos Dinámicas: Listas, Pilas, Colas y Árboles

Listas Simplemente Enlazadas

Constituyen una colección de elementos llamados nodos. El orden entre estos se establece por medio de punteros, es decir, direcciones o referencias a otros nodos.

Listas Doblemente Enlazadas Lineales

Son una colección de nodos ordenada según su posición, tal que cada uno de ellos es accedido mediante el puntero "anterior" del campo de enlace del nodo siguiente y por el puntero "siguiente" del campo de enlace del nodo anterior.

Listas Simplemente Enlazadas Circulares

Son una colección de elementos llamados nodos. El orden entre estos se establece por medio de punteros, es decir, direcciones o referencias a otros nodos.

Listas Doblemente Enlazadas Circulares

El campo de la liga izquierda del primer nodo apunta al último, y el campo de la liga derecha del último apunta al primero. La principal ventaja es que permite la navegación en cualquier sentido a través de la misma y, además, se puede recorrer toda la lista partiendo de cualquier nodo, siempre que tengamos un apuntador a este.

Encabezados

Este nodo no representa un elemento en la lista. Se usa para conservar información global sobre toda la lista.

Pilas

Tipo de dato abstracto dinámico homogéneo al que solo se tiene acceso por la cabeza (tipo LIFO - Last In, First Out). Los operadores básicos son "meter" y "sacar" elementos de la pila. Los operadores auxiliares son "inicia", "vacía", "llena" y "consultar".

Colas

Es un tipo de dato abstracto dinámico homogéneo (tipo FIFO - First In, First Out) al que solo se tiene acceso al principio de la cola para sacar elementos y al final de la misma para meterlos. Los operadores básicos son "sacar" y "meter" elementos, y sus operadores auxiliares son "inicia", "vacía", "llena" y "consulta".

Árboles

Es una estructura jerárquica que se aplica sobre una colección de elementos u objetos llamados nodos, uno de los cuales es conocido como raíz. Los árboles tienen una gran variedad de aplicaciones, por ejemplo, representar fórmulas matemáticas, análisis de circuitos, etc.

• Todo nodo que no tiene hijos se llama terminal u hoja.
• Todo nodo que no es raíz ni hoja es interior.
• Grado: es el número de descendientes directos de un determinado nodo.
• Grado del árbol: es el máximo número de grados que hay en el árbol.
• Nivel: es el número de arcos que deben ser recorridos para llegar al nodo. La raíz es nivel 1.
• Altura: es el máximo nivel del árbol.

Árbol Binario

Es un árbol en el que cada nodo puede tener como máximo 2 subárboles.

Árbol binario completo: es un árbol en el que todos sus nodos, excepto los del último nivel, tienen 2 hijos.

El número de nodos de un árbol binario completo de altura h se puede calcular de la siguiente manera: 2^h - 1 (es decir, 2 elevado a la altura - 1).

Árbol Binario de Búsqueda

Es una estructura eficiente sobre la cual se pueden realizar las operaciones de búsqueda, inserción y eliminación. En donde todos los nodos del subárbol izquierdo *A* deben ser menores o iguales al nodo *A*, y los del derecho, mayores.

El árbol binario de búsqueda es una estructura de datos sobre la cual se pueden utilizar búsqueda, inserción y eliminación, pero también pueden llegar a ser costosas.

struct nodo {
    int dato;
    struct nodo *izq;
    struct nodo *der;
};

struct nodo *inicializa(struct nodo *R) {
    R = NULL;
    return R;
}

void (mayorOMenor)(struct nodo *R) {
    if (!vacia(R))
        while (R->(derOIzq) != NULL)
            R = R->(derOIzq);
    printf("%d", R->dato);
}