我正在使用霍夫曼编码，目前正处于将文本文件编码/解码为二进制文件的阶段。我有这段代码可以从树中检索一个节点及其所有相关数据(字符、频率、路径):
EmptyString ( string );
while ( ( c = fgetc ( nameTextFile ) ) != EOF ) {
nodeHuffmanTree = SearchHuffmanTree ( rootHuffmanTree, c );
strcpy ( string, nodeHuffmanTree -> route );
Encode ( nameBinaryFile, string );
EmptyString ( string );
}
假设已经为每个节点(0 和 1)生成了路由。我想要的 SearchHuffmanTree 函数是，给定一个字符，它在哈夫曼树中搜索所述字符，并返回包含它的节点。这是相关的，因为该节点将包含 Encode 函数将转换为字节的路由。
我知道我不能像二叉搜索树一样对待霍夫曼树，因为它不具有相同的特征，所以如果我想搜索特定字符，我将不得不遍历整棵树。
我已经在寻找不使用递归(和一些堆栈)的替代方案，虽然它们更容易理解，但它们产生的代码却相当不简单和干净，所以我更喜欢使用递归的解决方案。
我已经弄清楚了编码/解码部分，所以这几乎是最终完成我的代码的最后一步。期待您能给我的任何帮助。
最佳答案
是的，您不能假设任何特定节点(即字符)在树中的位置，因为节点的位置取决于字符的频率而不是它们的值。因此，您必须找到一种方法来遍历整棵树，而不做任何假设。
通常有两种遍历图的方法:基于队列的广度优先搜索 (BFS) 和基于堆栈的深度优先搜索 (DFS)。
由于 DFS 是基于堆栈的，所以它本质上是一个递归问题。此外，由于 2 种方法遍历树的方式不同，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 - 如何递归遍历哈夫曼树以搜索特定元素？ - C，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34406972/