C/Visual C - ESTUDIANTE

#include <iostream>

#include <queue>

#include <vector>

#include <unordered_map>

#include <string>

using namespace std;

struct Nodo {

    int frecuencia;

    char dato;

    int hi; // Índice del hijo izquierdo

    int hd; // Índice del hijo derecho

    // Constructor

    Nodo(int f, char d) : frecuencia(f), dato(d), hi(-1), hd(-1) {}

};

// Comparador para la cola de prioridad

struct Comparador {

    bool operator()(const Nodo* a, const Nodo* b) {

        return a->frecuencia > b->frecuencia; // Menor frecuencia tiene mayor prioridad

    }

};

// Función para construir el árbol de Huffman

Nodo* construirArbolHuffman(const vector<pair<char, int>>& frecuencias) {

    priority_queue<Nodo*, vector<Nodo*>, Comparador> cola;

    // Crear nodos y agregarlos a la cola de prioridad

    for (const auto& par : frecuencias) {

        cola.push(new Nodo(par.second, par.first));

    }

    // Construir el árbol

    while (cola.size() > 1) {

        Nodo* izquierda = cola.top(); cola.pop();

        Nodo* derecha = cola.top(); cola.pop();

        // Crear un nuevo nodo que combine los dos nodos

        Nodo* nuevoNodo = new Nodo(izquierda->frecuencia + derecha->frecuencia, '\0');

        nuevoNodo->hi = izquierda->frecuencia; // Guardar la frecuencia del hijo izquierdo

        nuevoNodo->hd = derecha->frecuencia;   // Guardar la frecuencia del hijo derecho

        // Agregar el nuevo nodo a la cola

        cola.push(nuevoNodo);

    }

    return cola.top(); // Retornar la raíz del árbol

}

// Función para imprimir el árbol de Huffman

void imprimirArbol(Nodo* raiz, const string& codigo) {

    if (!raiz) return;

    // Si es una hoja, imprimir el carácter y su código

    if (raiz->dato != '\0') {

        cout << "Carácter: " << raiz->dato << " Código: " << codigo << endl;

    }

    // Recursión para los hijos izquierdo y derecho

    imprimirArbol(raiz->hi, codigo + "0");

    imprimirArbol(raiz->hd, codigo + "1");

}

int main() {

    // Frecuencias de los caracteres

    vector<pair<char, int>> frecuencias = {

        {'a', 5},

        {'b', 9},

        {'c', 12},

        {'d', 13},

        {'e', 16},

        {'f', 45}

    };

    // Construir el árbol de Huffman

    Nodo* raiz = construirArbolHuffman(frecuencias);

    // Imprimir los códigos de Huffman

    cout <<"Códigos de Huffman:" << endl;

    imprimirArbol(raiz, "");

    return 0;

}