Есть алгоритм Хаффмана.
Пытаюсь реализовать функцию вывода дерева (traversal());
и вроде все верно, но выводится мусор
joxi.ru/L210kYWI6oP86m
На сервисе cpp.sh все корректно выводится.
С VS знаком плохо. Может нужно поток как-то чистить или проверять кодировку ?
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <iterator>
//#include <conio.h>
using namespace std;
class Node {
public:
int a;
char c;
Node *left, *right;
bool operator< (Node t) const
{
return a < t.a;
}
Node() {};
Node(Node *L, Node *R)
{
left = L;
right = R;
a = L->a + R->a;
}
};
struct Compare{
bool operator() (Node *l, Node *r) const
{
return l->a < r->a;
}
};
void traversal(Node* root,unsigned k);
int main()
{
string s = "my son is my sun!";
map<char,int> M;
for (int i = 0; i < s.length(); i++)
{
M[s[i]]++;
}
list<Node*> Tree;
map<char, int>::iterator M_itr;
for (M_itr = M.begin(); M_itr !=M.end(); ++M_itr)
{
Node* one = new Node;
one->c = M_itr->first;
one->a = M_itr->second;
Tree.push_back(one);
}
list<Node*>::iterator L_itr;
for (L_itr = Tree.begin(); L_itr != Tree.end(); L_itr++)
{
cout << (*L_itr)->c << ":" << (*L_itr)->a << endl;
}
while (Tree.size()!=1)
{
Tree.sort(Compare());
Node *son_L = Tree.front();
Tree.pop_front();
Node *son_R = Tree.front();
Tree.pop_front();
Node *parent = new Node(son_L,son_R);
Tree.push_back(parent);
}
cout << endl;
Node* root = Tree.front();
traversal(root,0);
return 0;
//getch();
}
void traversal(Node* root, unsigned k)
{
if (root)
{
for (unsigned i = 0; i < k; i++)
{
cout << "";
}
if (root->c) cout << root->a << " (" << root->c << ")" << endl;
else cout << root->a << endl;
traversal(root->left,k+3);
traversal(root->right,k+3);
}
}