¿Cómo implemento la codificación y decodificación de Huffman usando una matriz y no un árbol?
Según cómo se formule la pregunta, supondré que sabes cómo hacerlo con un árbol. Entonces, la verdadera pregunta es cómo implementar un árbol en una matriz.
Cada nodo del árbol puede indexarse usando un número entero, que se convertirá en la posición del nodo en la matriz.
- ¿Es esta una función de clasificación de burbujas válida? Si es así, ¿entonces cómo?
- ¿Cuál es su opinión sobre Interview Cake para resolver algoritmos?
- ¿Qué algoritmos de máquina requieren escala / normalización de datos?
- ¿Qué consejos y técnicas puedo aprender para retener mi comprensión de algoritmos y estructuras de datos?
- ¿Cuál es la implementación más rápida del árbol de búsqueda binario? (auto-equilibrio)
Existen varios esquemas para indexar los nodos. Probablemente lo mejor para los árboles binarios es: raíz: = 1, hijo izquierdo: = 2 * n, hijo derecho: = 2 * n + 1. Un árbol Huffman es un árbol binario, por lo que esta codificación funcionará, pero habrá muchas posiciones vacías en la matriz. Dependiendo de qué tan grandes sean los nodos de su árbol Huffman, podría ser mejor construir una matriz de indexación utilizando el esquema anterior y que contenga punteros / índices a otra matriz que contenga los datos reales. O puede intentar pensar en una mejor asignación de índices a nodos.
El resto del códec debería funcionar exactamente de la misma manera que con un árbol. La única diferencia está en cómo accede a las estructuras de datos.
