java - ハフマン木でパスを探す

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);