Кодирование Хаффмана приводит к неправильному выводу, но правильной длины

Question

Я пытаюсь реализовать дерево Хаффмана для сообщений декодирования / кодирования как часть назначения. Я, кажется, ошибаюсь где-то в коде, так как получаю правильную длину и могу подтвердить, выполнив порядок уровней.

Где я делаю не так? Хотелось бы некоторые советы или рекомендации

Я пробовал много разных реализаций очереди minHeap / priority, но текущее состояние кода является наиболее близким к достижению результата.

package main

import (
    "fmt"
    "sort"
)

const nullchar = '\x00'

type treeNode struct {
    left, right *treeNode
    letter      rune
    frequency   int
}

type tree struct {
    root *treeNode
}

func makeNode(letter rune) *treeNode {
    return &treeNode{
        letter:    letter,
        frequency: 1,
    }
}

func makePriorityQueue(letters []*treeNode, byAlpha bool) {

    // sort queue into priotiry queue after frequency
    sort.Slice(letters, func(i, j int) bool {
        if byAlpha {
            return letters[i].letter < letters[j].letter
        }

        return letters[i].frequency < letters[j].frequency
    })
}

func mapRunesToNodes(message string) []*treeNode {
    letters := make([]*treeNode, 0)

    for _, letter := range message {

        containsLetter := false
        for _, node := range letters {
            if node != nil && node.letter == letter {
                node.frequency++
                containsLetter = true
                break
            }
        }

        if !containsLetter {
            letters = append(letters, makeNode(letter))
        }
    }

    return letters
}

func printPriorityQueue(letters []*treeNode) {
    for _, node := range letters {
        if node != nil {
            fmt.Println(node)
        }
    }
}

func makeHuffmanTree(letters []*treeNode) *tree {

    tree := new(tree)
    if len(letters) == 1 {
        tree.root = letters[0]
        return tree
    }

    for len(letters) > 1 {

        root := &treeNode{
            letter:    nullchar,
            left:      letters[0],
            right:     letters[1],
            frequency: letters[0].frequency + letters[1].frequency,
        }

        letters = append(letters, root)
        letters = append(letters[:0], letters[2:]...)

        makePriorityQueue(letters, false)
    }

    tree.root = letters[0]
    return tree
}

func levelOrder(root *treeNode) [][]int {
    res := [][]int{}
    var dfs func(*treeNode, int)

    dfs = func(root *treeNode, level int) {
        if root == nil {
            return
        }

        if level >= len(res) {
            res = append(res, []int{})
        }
        res[level] = append(res[level], root.frequency)

        dfs(root.left, level+1)
        dfs(root.right, level+1)
    }

    dfs(root, 0)

    return res
}

func (root *treeNode) isLeaf() bool {
    return root.left == nil && root.right == nil
}

// visit current subtree
func (root *treeNode) traverse(encodeMap *map[rune]string, code string) *map[rune]string {

    if root == nil {
        return encodeMap
    }

    if root.isLeaf() {
        (*encodeMap)[root.letter] = code
    }

    root.left.traverse(encodeMap, code+"0")
    root.right.traverse(encodeMap, code+"1")

    return encodeMap
}

func encode(root *treeNode) map[rune]string {

    encodedMap := make(map[rune]string)
    root.traverse(&encodedMap, "")
    fmt.Println(encodedMap)
    return encodedMap
}


func main() {
    toEncode := "i love computer science"
    toDecode := "110010111010000110111111011000000111000110010011111110100101010110011001110110100111"

    queue := mapRunesToNodes(toEncode)
    makePriorityQueue(queue, true)
    //printPriorityQueue(queue)

    huffmanTree := makeHuffmanTree(queue)

    /*level := levelOrder(huffmanTree.root)
    num := 0
    for i, l := range level {
        fmt.Printf("LEVEL %d: %v\n", i+1, l)
        num += len(l)
    }

    fmt.Printf("NUM NODES: %d\n", num)*/

    encodedMap := encode(huffmanTree.root)

    output := ""
    for _, v := range toEncode {
        output += encodedMap[v]
    }

    fmt.Printf("\n\nMATCHING: %v\nENCODED: %s\nTARGET:  %s\n", output == toDecode, output, toDecode)

    /*for k, v := range encodedMap {
        fmt.Printf("%s %s\n", string(k), v)
    }*/
}

Я ожидаю, что результат переменной "toEncode" будет равен переменной "toDecode" после выполнения кодирования в строке.

Примечание учителя, которое может помочь при отладке: «При первоначальном добавлении символов в приоритетную очередь вставьте символы в Алфавитный порядок. Например, если ваша частотная карта: b: 2, c: 1, x: 1, a: 4, [пробел]: 3 тогда вы добавите их в очередь приоритетов в следующем порядке: [пробел], a, b, c, x. "