java - ハフマン木をたどる

Question

だから現在、私はハフマン木を作成するプログラムを持っています。ツリーは、次のフィールドを持つ「H ノード」で構成されます。ノードに含まれる文字)。

リンク リストからノードを追加してハフマン ツリーを作成しました。ツリーが正しく作成されたことはわかっています。ツリーを作成するときに、親ノードを指定したときにノードに伝えました。それが親の「右」の場合、そのコード文字列は 1 で、左の場合は 0 です。ただし、明らかにツリー全体が作成された後、各ノードは0 か 1 のどちらかしかありませんが、まだ 00100101 のような文字列はありません。私の質問は、このツリーを取得したので、それをたどることができますか? 各子に親のコードと子自身のコードを与えるという考えは理解していますが、これを達成するためにツリーをループする方法がわかりません。

前もって感謝します。

Answer 1

もしかしてこれ？

  ExpandBinaryPaths(node, prefix)
  1. if node is null then return 
  2. else then
  3.    node.binary = prefix concat node.binary
  4.    ExpandBinaryPaths(node.left, node.binary)
  5.    ExpandBinaryPaths(node.right, node.binary)
  6.    return

アイデアは、プレフィックスなしでルートでこれを呼び出すことです... ExpandBinaryPaths(root, "")。