package main
 
import (
    "bytes"
    "fmt"
)
 
// 定义节点类型
type Node struct {
    Weight int
    Left   *Node
    Right  *Node
}
 
// 构建哈夫曼树
func buildHuffmanTree(weights []int) *Node {
    var nodes []*Node
    for _, weight := range weights {
        nodes = append(nodes, &Node{Weight: weight})
    }
 
    for len(nodes) > 1 {
        // 排序节点，按照权重从小到大
        sortNodes(nodes)
 
        // 取出最小的两个节点创建新节点
        a, b := nodes[0], nodes[1]
        newNode := &Node{Weight: a.Weight + b.Weight, Left: a, Right: b}
 
        // 删除已经处理的两个节点
        nodes = append(nodes[:0], nodes[2:]...)
 
        // 将新节点加入到节点列表中
        nodes = append(nodes, newNode)
    }
 
    return nodes[0]
}
 
// 对节点列表进行排序
func sortNodes(nodes []*Node) {
    for i := range nodes {
        for j := i; j > 0 && nodes[j].Weight < nodes[j-1].Weight; j-- {
            nodes[j], nodes[j-1] = nodes[j-1], nodes[j]
        }
    }
}
 
// 哈夫曼编码
func huffmanEncoding(root *Node, encoding map[byte]string) {
    var traverse func(node *Node, code string)
    traverse = func(node *Node, code string) {
        if node.Left == nil && node.Right == nil {
            encoding[byte(node.Weight)] = code
            return
        }
        traverse(node.Left, code+"0")
        traverse(node.Right, code+"1")
    }
 
    traverse(root, "")
}
 
// 哈夫曼解码
func huffmanDecoding(root *Node, data string) string {
    var result bytes.Buffer
    current := root
    for i := range data {
        if current.Left == nil && current.Right == nil {
            result.WriteByte(byte(current.Weight))
            current = root
            continue
        }
        if data[i] == '0' {
            current = current.Left
        } else if data[i] == '1' {
            current = current.Right
        }
    }
    return result.String()
}
 
func main() {
    // 示例：文本"aaabbbbccccddddeeeee"的哈夫曼编码和解码
    text := "aaabbbbccccddddeeeee"
    weights := make([]int, 27) // 字母从'a'到'z'的权重
 
    // 统计每个字符的权重
    for _, char := range text {
        weights[char-'a']++
    }
 
    // 构建哈夫曼树
    root := buildHuffmanTree(weights)
 
    // 生成哈夫曼编码
    encoding := make(map[byte]string)
    huffmanEncoding(root, encoding)
 
    // 示例：打印每个字符的哈夫曼编码
    for char, code := range encoding {
        fmt.Printf("%c: %s\n", char, code)
    }
 
    // 使用哈夫曼编码对文本进行编码
    var encoded bytes.Buffer
    for _, char := range text {
        encoded.WriteString(encoding[byte(char)])
    }
    encodedText := encoded.String()
    fmt.Printf("Encoded text: %s\n", encodedText)
 
    // 使用哈夫曼树对编码文本进行解码
    decodedText := huffmanDecoding