c++ - ハフマン木作成 C++

Question

変数として Node *left と Node *right を持つクラス Node があります。これで、次のようにハフマン ツリーを構築する関数ができました。

int x = pQueue.size();

for(int i=0;i<x-1;i++){

    Node *z = new Node;
    z->left = &pQueue.extractMin();
    z->right = &pQueue.extractMin();
    z->setchar(NULL);
    z->setfrequency(z->left->getFrequency() + z->right->getFrequency());
    pQueue.insert(z);

}

ハフマン木を作成する標準機能です。しかし、問題はこれです。最初に新しい Node* z が作成され、その左右の子が割り当てられると、ループの次の実行中に z の左右の子が再割り当てされ、最初に割り当てられた値が失われます。ループを実行するたびに新しいオブジェクトが作成され、その左右の子のメモリ位置が異なるという印象を受けました。しかし、これは起こっていません。ループが実行されるたびに新しいオブジェクトを作成するにはどうすればよいですか??

これが私が得ているものです

頻度 14 のノードをチェックすると、最初の実行でいくつかのメモリ位置がその左右の子として割り当てられます。ただし、次の実行では、頻度 14 ノードの左右の子は null であり、頻度 25 ノードの子は前の場所に設定されます。周波数 14 ノードの最初のラウンドと周波数 25 ノードの新しい場所で割り当てられるのは同じであると期待しています。

Answer 1

あなたが言ったように、pQueueがNodeオブジェクトのベクトルである場合（そして私はstd::vectorを想定しています-そうでない場合は答えを無視してください！）、vector::insert（）を使用して、実際にはイテレータを追加していますノード オブジェクト。代わりに次のようにしてみてください。

int x = pQueue.size();

for(int i=0;i<x-1;i++){

    Node z;
    z.left = &pQueue.extractMin();
    z.right = &pQueue.extractMin();
    z.setchar(NULL);
    z.setfrequency(z.left->getFrequency() + z.right->getFrequency());
    pQueue.push_back(z);
}