在哈夫曼树上搜索路径

Question

我正在研究霍夫曼树，我试图弄清楚如何遍历树以找到具有我正在寻找的字符的节点。在搜索树时，我需要使用 1 和 0（0 左 1 右）保留通往我正在查找的节点的路径字符串。我该怎么做？

Answer 1

自从我写霍夫曼引擎以来已经很长时间了，但我会尝试一下。

伪代码。

假设你的霍夫曼树节点看起来像这样

class HuffNode
{
...
char ch;
long huffCode; //initialized to zero initially
HuffNode left,right;
}

所以这里的递归函数（将其转换为迭代应该很容易）

void buildCodes(HuffNode currentNode, long currentCode)
{
currentNode->huffCode =  currentCode;
if(currentNode->left != null) buildCodes(currentNode->left, currentCode << 1);
if(currentNode->right != null) buildCodes(currentNode->right, (currentCode << 1) | 1);
}

这样调用它

buildCodes(rootHuffNode,0);