如何递归遍历哈夫曼树以搜索特定元素？ - C

Question

我正在使用 Huffman 编码，目前正处于 encoding/decoding 将文本文件转换为二进制文件的阶段。我有这段代码可以从树中检索一个节点及其所有相关数据（字符、频率、路由）：

EmptyString ( string );
while ( ( c = fgetc ( nameTextFile ) ) != EOF ) {
    nodeHuffmanTree = SearchHuffmanTree ( rootHuffmanTree, c );
    strcpy ( string, nodeHuffmanTree -> route );
    Encode ( nameBinaryFile, string );
    EmptyString ( string );
}

假设已经为每个节点（0 和 1）生成了路由。我想要的 SearchHuffmanTree 函数是，给定一个字符，它会在哈夫曼树中搜索该字符，然后 returns 我找到包含它的节点。这是相关的，因为该节点将包含 Encode 函数将转换为字节的路由。

我知道我不能像二叉搜索树那样对待哈夫曼树，因为它不具有相同的特征，所以如果我想搜索特定字符，我将不得不遍历整棵树.

我已经在寻找不使用递归（和一些堆栈）的替代方案，虽然它们更容易理解，但它们产生的代码却相当不简单和干净，所以我更喜欢使用递归的解决方案。

我已经弄清楚了 encoding/decoding 部分，所以这几乎是最终完成我的代码的最后一步。期待您能给我的任何帮助。

Answer 1

是的，您不能假设任何特定节点（即字符）在树中的位置，因为节点的位置取决于字符的频率而不是它们的值。因此，你将不得不找到一种方法来遍历整棵树，而不做任何假设。

通常有两种遍历图的方法：基于队列的广度优先搜索 (BFS) 和基于堆栈的深度优先搜索 (DFS)。

由于DFS是基于栈的，所以它本质上是一个递归问题。此外，由于两种方法遍历树的方式不同，DFS 在您的情况下平均效率更高。

DFS 是如何工作的？

嗯，基本原则是，如果一个节点不是叶节点，则对其每个子节点执行 DFS。如果选择遍历子树的顺序，可以先走概率最大的路径，这样可以增加更快找到结果的几率。

下面是一个简单的算法伪代码：

DFS(node T, char x) {
    if (T is leaf)
        if (T == x)
            return found
        else
            return not found
    else
        foreach child of T
            if DFS(child, x) == found
                return found
        return not found

您可以在 DFS 的维基百科页面上找到更多详细信息。

如何递归遍历哈夫曼树以搜索特定元素？ - C

How to traverse a Huffman Tree recursively in search for an specific element? - C

c

recursion

huffman-code