遍历哈夫曼树

Question

所以目前我有一个创建霍夫曼树的程序。树由具有以下字段的“Hnode”组成： 右（指向右子节点） 左（指向左子节点） 代码（整数字符串，理想情况下 0 和 1 将成为该节点的霍夫曼代码） 字符（节点中包含的字符）。

我通过从链表添加节点来创建哈夫曼树 - 我知道树已正确创建。当我创建树时，当我给它一个父节点时，我告诉节点，如果它是父节点的“右”，则其代码字符串为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, "")。