0

私は C++ プログラムと私のグループに取り組んでいますが、inOrder トラバーサルを使用してプレフィックス コードを生成する方法についてのロジックを理解できません。PrefixCode ツリーが構築されており、そこからコードを生成したいと考えています。

ロジックに問題があるため、コードを提供する必要があるかどうかわかりません。必要な場合はお知らせください。

ありがとう。

4

1 に答える 1

1

ご指摘の通り、よくわかりません。買ってみます...

まず、ツリーが正しく構築されていることを前提としています。

次に、各リーフには、エンコードされるシンボルが含まれています。各シンボルのコードは、ルートからリーフまでのパスによって定義されます。最初、ルートにいるとき、コードは空です。左に行くと、a0をコードに連結します。対称的に、右に行くと連結し1ます。

第三に、ペアのリストが必要だと仮定します<symbol, code>。symbol文字でありcode、接頭辞コードを含む文字列です。結果は、ツリーによって表されるすべてのシンボルとそのコードのリストです。

現在、そのリストを生成するためのアルゴリズムは、ルートから現在のノードまでのプレフィックスを格納するためにスタックを使用します。葉に到達するたびに、コードはスタックに入れられますが、逆になります。このようなアルゴリズムは次のようになります。

void codes(Node * root, stack<char> & s)
{
  if (is_leaf(root))
    {
      auto symbol = // symbol stored in the node
      string code = // the reversed stack content; that is the code of current leaf
      cout << symbol << " = " << code << endl;
    }

  s.push('0');
  codes(LLINK(root), s);
  s.pop();

  s.push('1');
  codes(RLINK(root), s);
  s.pop();
}

ルートからノードへの部分パスを格納するための「自然な」データ構造であるため、スタックを提案します。しかし、多分それはより良いでしょうvector<char>. この場合、 と で置き換える必要がpush()ありpush_back()ます。ただし、リバース イテレータを使用してコードを作成できるという利点があります。pop()pop_back()

また、 instruction の代わりにcout ...、リストまたはベクトルを使用してペアを挿入することもできます。その後、必要に応じて並べ替えることができます。または、バイナリ検索ツリーなどの「自然に並べ替えられた」データ構造を使用して、並べ替えを避けることもできます。もちろん、興味がある場合は、シンボル出力でソートされたものを生成することです。

お役に立てば幸いです

于 2015-10-23T02:05:59.363 に答える