递归树遍历，为树的每个叶子返回一个变量

Question

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

比方说，我有这样的树：

  3\65 

     6\-1 

      3\70 

    9\-1 

      2\66 

     3\-1 

      1\67 
16\-1 

    7\68 

每片叶子（68分之7，67分之1，66分之2，7/70，3/65）有一个名为 “编码” 的成员，该是一个字符串。

（即每个节点都有一个节点 - >左，节点 - >右，和节点 - >编码）

比方说，编码如下：

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 

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

我想不出如何在树外保存这些东西。 “

Answer 1

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

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

OK，无论哪种方式（并没有给该源代码的距离）你只是：

• 创建一个足够大的（*）阵列启动递归

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

将指向该指针的指针作为新的/附加函数参数赋予递归。每次在递归到达叶你

• 写入指针，你发现在叶
• 增加指针什么（你可以做到这一点，因为你有的指针的指针

Answer 2

据我所知，在huffman代码实现中，你不必使用外部数组，最简单的方法是在你的结构中增加另一个指针（'next'） 每个元素链接两次。一次作为树的成员，一次作为链接列表的成员。 这样就不需要新的结构。