# Thread: yet another huffman tree problem

1. ## yet another huffman tree problem

Code:
```#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define NONE_FOUND 30000
using namespace std;
struct node {
node* one;
node* zero;
node* parent;
char value;
int amount;
node (int x) {
one=NULL;
zero=NULL;
value=x;
amount=1;
parent=NULL;
}
amount++;
}
};

class huffman_tree {

public:
vector<node*> node_list;
vector<int> code_temp;

int search(int x) {
for (int i=0;i<node_list.size();i++)
if (node_list[i]->value==x)  return i;
return NONE_FOUND;
}

int temp=search(x);
if (temp!=NONE_FOUND)
else node_list.push_back(new node(x));
}

void bubblesort()  {
node* temp;
int n=node_list.size();
for (int i=0;i<n-1;++i)
for (int j=1;j<n-i;++j)
if (node_list[j-1]->amount > node_list[j]->amount) {
temp=node_list[j];
node_list[j]=node_list[j-1];
node_list[j-1]=temp;

}
}

void sort_it() {
bubblesort();
}

void huff() {

while (node_list.size() > 1) {

join (node_list[0],node_list[1]);
node_list.erase(node_list.begin(),node_list.begin()+1);
node_list[0]=node_list[0]->parent;
int place=0;
while (node_list[place] -> amount <= node_list[0]->amount && place < node_list.size()) place++;
node_list.insert(node_list.begin()+place,node_list[0]);  //find place
node_list.erase(node_list.begin(),node_list.begin()+1);

}
}
void join(node* a, node* b) {
node* parent;
parent=node_list[node_list.size()-1];
b->parent=parent;
a->parent=parent;
parent->one=b;
parent->zero=a;
a->parent->amount=a->amount+b->amount;

}
void print_tree() {
cout << node_list[0]->value;
cout << node_list[0]->zero->value;
/*this function used mostly for debugging */
}
void lookup() {

get_letters(node_list[0]); //all values should have been stored in the code_temp vector array
while (code_temp.size()) {
code_temp.erase(code_temp.begin(),code_temp.begin()+1);
cout << code_temp[0];  //show the results, this is gonna be changed later
}
}
int get_letters(node* x) {

if (x->zero!=NULL) { code_temp.push_back(0); /*next statement added for debugging */
cout << x->zero << " "; get_letters(x->zero); }
if (x->one!=NULL)  { code_temp.push_back(1); get_letters(x->one); }

}

};

int main()
{
huffman_tree tree;

string temp="yabba dabba doo";
char letter;
while (temp.length()) {
letter=temp.at(0);
temp.erase(0,1);
}
tree.sort_it();
tree.huff();
tree.print_tree();
tree.lookup();
}```
if this code looks familiar, it's because i posted a few days ago concerning a problem. basicly, this code causes a stack overrun. what's happening is after linking the nodes together in a huffman coding manner(which i think it's messing up on), the lookup function is supposed to probe each tree limb and print a code for each letter.
i think that for some reason, by some mistake, a node points to itself. (i've confirmed this with cout statements until it complains of stack overrun). can anyone spot why this is happening?

some other info:
most everything else works, until the huffman tree is created. the vector array node_list stores and sorts the nodes by frequency. each node has a parent pointer, a one pointer, and a zero pointer. the zero and one pointers point further down the tree, while the parent pointer goes up.
huff() is supposed to organize the nodes into a tree. the nodes are assumed already sorted into order by frequency. the two lowest nodes are combined using the join function. one node is removed from the array, and the other one is replaced by its newly created parent node. then the parent node is sorted back into line. this process repeats until only one node is left.

2. here's the simplified code:
Code:
```struct node {
node* one;
node* zero;
node* parent;
char value; //letter
int amount; //number of letters
node (int x) {
one=NULL; //for some reason this changes as it progresses through the code
zero=NULL;//ditto
value=x;
amount=1;
parent=NULL;
}
};

class huffman_tree {
public:
vector<node*> node_list; //an array of nodes. once they get linked into a tree everything will be under node_list[0]
vector<int> code_temp; // a fairly global solution, will change later

int search(int x); //if the character 'x' is found in the node_list, return its location

void bubblesort(); //sort node_list by frequency (ie, by amount)
void sort_it(); //calls bubblesort for now, will change later to better sorting method

void huff() {
//while there's still two nodes left:
//call join(), join node_list[0] and node_list[1]
//remove two nodes from beginning, replace with their parent
//locate the right space to insert the new parent node
//move the parent node there
}

void join(node* a, node* b) //make a node, put two other nodes under it
{
//call add function to create new node with value of 1 to distinguish it from letter nodes
//assign temp. 'parent' pointer to newly created node
//point the two nodes' parent pointers at it
//point ther parent's two children pointers at the two nodes
//make the parent node's amount the sum of the children nodes
}
void print_tree() ; //debugging purposes
void lookup() //create lookup table
{
//call get_letters(top node)
//then print the code
}
int get_letters(node* x) {
//if x's zero pointer is pointing to something, push a zero into the buffer
//if x's one pointer is pointing to something, push a one into the buffer
//in either case, call get_letters for a node under this one
}
};

int main()
{
huffman_tree tree;

string temp="yabba dabba doo";
char letter;
while (temp.length()) {  //add 'temp' into huffman list
letter=temp.at(0);
temp.erase(0,1);
}
tree.sort_it();  //sort tree by 'amount' value: 0 is smallest
tree.huff(); // organize into huffman table
tree.print_tree(); //right now it does practicly nothing
tree.lookup(); // organize tree into lookup table
}```
hope it helps:

3. solved it by rewriting the code. got rid of join(), and rewrote huff() like this:
Code:
```void huff() {
while (node_list.size() > 1) {
node_list[0]->parent=new node(1); /// transform two nodes into its parent node
node_list[0]->parent->zero=node_list[0];
node_list[0]->parent->one=node_list[1];
node_list[1]->parent=node_list[0]->parent;
node_list.erase(node_list.begin(),node_list.begin()+1);
node_list[0]=node_list[0]->parent;
node_list[0]->amount=node_list[0]->zero->amount + node_list[0]->one->amount;

sort_it();  //a cheap way to sort it back
//repeat
}
}```
simplicity rocks. (yes, i know it's very wasteful to sort the whole list every single loop instead of just moving the node, but i'm tired and bug-prone)