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」と呼ばれるメンバーがあります。

（つまり、各ノードには、ノード->左、ノード->右、およびノー​​ド->エンコーディングがあります）

エンコーディングが次のようになっているとしましょう。

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

「これらの文字列をツリーの外側の配列に保存してください。」

コメント：文字列を保存する必要がありますか？整数を格納し、再帰の終了後に文字列を作成すると、はるかにクリーンになります。

OK、どちらの方法でも（そしてソースコードを提供せずに）あなたはただ：

  • 再帰を開始する前に、十分な大きさの（*）配列を作成します

  • 配列のさまざまな部分への書き込みに使用されるポインターを作成し、そのポインターを配列の先頭に初期化します。

そのポインタへのポインタを、新しい/追加の関数引数として再帰に与えます。再帰で葉に到達するたびにあなたは

  • 葉で見つけたものをポインタに書き込みます
  • ポインターを増やします（ポインターへのポインターがあるため、これを行うことができます
于 2013-02-25T19:06:17.410 に答える
0

私が覚えている限り、ハフマンコードの実装では、外部配列を使用する必要はありません。これを実装する最も簡単な方法は、構造体に別のポインター（'next'）を追加することです。各要素は2回リンクされています。ツリーのメンバーとして1回、リンクリストのメンバーとして1回。このように、新しい構造は必要ありません。

于 2013-02-25T19:39:50.450 に答える