Я реализовал алгоритм Хаффмана приведенный в коде ниже. Однако, я столкнулся с проблемой кодирования "лепестков" полученного дерева. Я не могу найти ошибку, почему алгорим кодирования проходит только 1 раз.
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <functional>
#include <queue>
#include "string.h"
using namespace std;
struct Node //Звено дерева
{
int x; //То, что записываем в дерево
char s[1]; //Символ
Node *l,*r,*p; //Это указатели на новые звенья
char code[256]; //Код символа
};
class CompareLastDigits {
public:
bool operator()(Node x, Node y)
{ return x.x > y.x ;
}
};
void TraverseDFS(Node* node)
{
//We concatenate a 0 for each step to the left
if (node->l != NULL)
{
TraverseDFS(node->l);
}
//We concatenate a 1 for each step to the right
if(node->r != NULL)
{
TraverseDFS(node->r);
}
while (node->l == NULL && node->r == NULL)
{
Node* par = node;
while (par->p != NULL) {
strcat(node->code, par->p->s); //
par = par->p;
}
}
};
int main()
{
Node node[5];
priority_queue <Node, vector<Node>, CompareLastDigits > P;
int n = 5, i =0, j=0;
Node* nodeXY;
for (i=0;i<4;i++) {
node[i].x = i;
node[i].l = NULL;
node[i].r = NULL;
node[i].p = NULL;
node[i].code[0] = '\0';
}
for (i=0;i<4;i++) {
P.push(node[i]);
}
Node x[4], y[4];
i = 0;
while (P.size()!=1) {
x[i] = P.top();
P.pop();
y[i] = P.top();
P.pop();
nodeXY = new Node;
(*nodeXY).x = x[i].x + y[i].x;
if (x[i].x == y[i].x) {
Node temp = x[i];
x[i] = y[i];
y[i] = temp;
}
(*nodeXY).l = &x[i];
x[i].p = nodeXY;
y[i].p = nodeXY;
x[i].s[0] = '0';
y[i].s[0] = '1';
x[i].s[1] = '\0';
y[i].s[1] = '\0';
x[i].code[0] = '\0';
y[i].code[0] = '\0';
(*nodeXY).r = &y[i];
(*nodeXY).p = NULL;
//cout << "Retrieved element: " << (*nodeXY).x <<" " << (*nodeXY).l->x <<" " << (*nodeXY).r->x << endl;
P.push(*nodeXY);
++i;
}
nodeXY->s[0] = '\0'; //у вершины дерево заверш символ
TraverseDFS(nodeXY);
cout<<nodeXY->l->l->code; // по идее должен выдавать 00
cin.get();
return 0;
}
Так же не могли бы вы подсказать существует ли более простая реализация алгоритма?