哈夫曼解码( Scala)

import scala.collection.mutable

// 定义哈夫曼树的节点
case class HuffmanNode(value: Option[Char], frequency: Int, left: Option[HuffmanNode], right: Option[HuffmanNode])

object HuffmanDecoding {
  // 构建哈夫曼树
  def buildHuffmanTree(data: String): Option[HuffmanNode] = {
    val frequencyMap = mutable.Map[Char, Int]().withDefaultValue(0)
    for (c <- data) {
      frequencyMap(c) += 1
    }
    val priorityQueue = mutable.PriorityQueue[HuffmanNode]()(Ordering.by(-_.frequency))
    for ((char, frequency) <- frequencyMap) {
      priorityQueue.enqueue(HuffmanNode(Some(char), frequency, None, None))
    }
    while (priorityQueue.length > 1) {
      val left = priorityQueue.dequeue()
      val right = priorityQueue.dequeue()
      val newNode = HuffmanNode(None, left.frequency + right.frequency, Some(left), Some(right))
      priorityQueue.enqueue(newNode)
    }
    priorityQueue.headOption
  }

  // 解码数据
  def decodeData(data: String, huffmanTree: Option[HuffmanNode]): String = {
    def decodeHelper(node: HuffmanNode, remainingData: String, decodedData: String): String = {
      if (remainingData.isEmpty) {
        decodedData
      } else {
        node match {
          case HuffmanNode(Some(char), _, _, _) =>
            decodeHelper(huffmanTree.get, remainingData, decodedData + char)
          case HuffmanNode(None, _, Some(left), Some(right)) =>
            if (remainingData.head == '0') {
              decodeHelper(left, remainingData.tail, decodedData)
            } else {
              decodeHelper(right, remainingData.tail, decodedData)
            }
          case _ => decodedData
        }
      }
    }

    decodeHelper(huffmanTree.get, data, "")
  }

  def main(args: Array[String]): Unit = {
    val encodedData = "101100011110101001010"
    val huffmanTree = buildHuffmanTree("ABCD")
    val decodedData = decodeData(encodedData, huffmanTree)
    println(decodedData)  // 输出：ABACAD
  }
}