1

我有一个霍夫曼二叉树。我需要遍历树，直到到达每一片叶子，对于每一片叶子，我需要“保存”该叶子节点的一个成员，并将所有这些变量保存在树外的数组中。

假设我有这棵树：

            3\65

        6\-1

            3\70

    9\-1

            2\66

        3\-1

            1\67
16\-1

    7\68

每个叶子（7/68、1/67、2/66、7/70、3/65）都有一个名为“encoding”的成员，它是一个字符串。

（即每个节点都有一个node->left、node->right和node->encoding）

假设编码如下：

7/68 got an encoding of 0
1/67 got an encoding of 100
2/66 got an encoding of 101
3/70 got an encoding of 110
3/65 got an encoding of 111

我可以相对轻松地遍历树并打印出这些值，但我需要做的是将这些字符串保存在树外的数组中。

我想不出如何将这些保存在树外。

4

2 回答 2

0

据我记得，在霍夫曼代码实现中，您不必使用外部数组。实现它的最简单方法是将另一个指针（'next'）添加到您的结构中。每个元素链接两次。一次作为树的成员，一次作为链表的成员。这样就不需要新的结构。

于 2013-02-25T19:39:50.450 回答
0

“将这些字符串保存在树外的数组中。”

评论：你确定你必须存储字符串吗？如果你只存储整数并在递归完成后创建字符串，它会更干净。

好的，无论哪种方式（并且不泄露源代码），您只需：

  • 在开始递归之前创建一个足够大（*）的数组

  • 创建一个指针，用于写入数组的不同部分，将该指针初始化为数组的开头。

将指向该指针的指针作为新的/附加的函数参数提供给您的递归。每次在递归中到达叶子时，您

  • 将您在叶子上找到的内容写入指针
  • 增加指针（你可以这样做，因为你有指向指针的指针
于 2013-02-25T19:06:17.410 回答