Huffman/Tree

[mikecolistro]

Hello there!
Im making a huffman tree and im having troubles with the pointers. For somereason its not giving the correct output. The problem is where the l2 nodes are pointing.

#include <iostream>

/*
A=7	 B=2	 C=2 	D=3 	E=11 	F=2 	G=2
H=6	 I=6	 J=1	 K=1	 L=4	 M=3	 N=7
O=9	 P=2	 Q=1	 R=6	 S=6	 T=8	 U=4
V=1	 W=2	 X=1	 Y=2	 Z=1
*/

using namespace std;

typedef struct Node *BST;

struct Node{
	int freq;
	char letter;
	Node *right;
	Node *left;
};



Node * createNode(){
	struct Node *new1;
	new1 = (struct Node*) malloc(sizeof(struct Node));


	return new1;
}

Node  fillLeaf(char letter, int freq){
	Node new1;
	new1.letter = letter;
	new1.freq = freq;
	new1.left = NULL;
	new1.right = NULL;
	return new1;
}

Node fillParent(Node l1, Node l2){
	Node new1;
	new1.freq = l1.freq + l2.freq;
	new1.right = &l1;
	new1.left = &l2;

	return new1;
}

void main(){
	int x = 25;
	Node leaf[26];
	leaf[0] = fillLeaf('e',11);
	leaf[1] = fillLeaf('o',9);
	leaf[2] = fillLeaf('t',8);
	leaf[3] = fillLeaf('a',7);
	leaf[4] = fillLeaf('n',7);
	leaf[5] = fillLeaf('i',6);
	leaf[6] = fillLeaf('s',6);
	leaf[7] = fillLeaf('r',6);
	leaf[8] = fillLeaf('h',6);
	leaf[9] = fillLeaf('l',4);
	leaf[10] = fillLeaf('u',4);
	leaf[11] = fillLeaf('d',3);
	leaf[12] = fillLeaf('m',3);
	leaf[13] = fillLeaf('c',2);
	leaf[14] = fillLeaf('f',2);
	leaf[15] = fillLeaf('p',2);
	leaf[16] = fillLeaf('y',2);
	leaf[17] = fillLeaf('g',2);
	leaf[18] = fillLeaf('w',2);
	leaf[19] = fillLeaf('b',2);
	leaf[20] = fillLeaf('v',1);
	leaf[21] = fillLeaf('k',1);
	leaf[22] = fillLeaf('x',1);
	leaf[23] = fillLeaf('j',1);
	leaf[24] = fillLeaf('q',1);
	leaf[25] = fillLeaf('z',1);

	for(int i  = 0 ; i < 26; i++){
		cout << "\nthe value of leaf["<<i<<"] is the letter is "<<leaf[i].letter<< " and the frequency is " <<leaf[i].freq;
	}

	Node l2[13];
	int j = 12;
	for(int i = 0; i < 13; i++){
		l2[j] = fillParent(leaf[x],leaf[x-1]);
		x--;
		x--;
		j--;

	}

	for(int i  = 0 ; i < 13; i++){
		cout << "\nthe freq of parent["<<i<<"] is  "<<l2[i].freq<< " and its right leafs letter is " << l2[i].right->letter;
	}

I suspect the problem is in fillParent() function where it is assigning the pointers.

[Taywin]

You gave only fragment of codes with no comment. Anyway, after looking at your code, I have some unclear points with your code.

1)Why do you start your weight queue in descending order? Don't you need to do it in ascending order?
2)I am not sure why you need only 13 indices for your l2? Or you are trying to create a pair node array? I don't know why would you need that if you could simply take out a pair, create a node, and add to a BST while iterating through the original array?
3)What is "x" variable in the loop?
4)I guess you have all the rest of the code to built the tree up to the tree root?
5)What output are you seeing now? How could I have an idea of what the output is like when you give only partial code and said "not correct output"?

[mikecolistro]

Hey sorry for the late response i was busy with midterms.
1) Isn't it going in ascending order, the weights are given then added into a new node.
2) Well since its a huffman tree it has to make starting from the leafs to the root. Since there are 26 letters in the alphabet i just made each level the ground function of half of the previous. I also tried to have an array of nodes for each level because thats the only way i could think of making a tree starting from the leafs.
3) The "x" variable was just the number of nodes in the previous level.
4) Yes the problem happened in every level so I figured just to put up to the second level. I also pasted it wrong without ending the main function but if i ended the main function there it should have compiled properly.
5) I apologize for the amateur mistake.

Anyways here is the full code but now the problem i have doesn't exist where im creating the root, as you can see if you compile it. So the problem is me having an array of nodes it would seem.

#include <iostream>

/*
A=7	 B=2	 C=2 	D=3 	E=11 	F=2 	G=2
H=6	 I=6	 J=1	 K=1	 L=4	 M=3	 N=7
O=9	 P=2	 Q=1	 R=6	 S=6	 T=8	 U=4
V=1	 W=2	 X=1	 Y=2	 Z=1
*/

using namespace std;

typedef struct Node *BST;

struct Node{
	int freq;
	char letter;
	Node *right;
	Node *left;
};



Node * createNode(){
	struct Node *new1;
	new1 = (struct Node*) malloc(sizeof(struct Node));


	return new1;
}

Node  fillLeaf(char letter, int freq){
	Node new1;
	new1.letter = letter;
	new1.freq = freq;
	new1.left = NULL;
	new1.right = NULL;
	return new1;
}

Node fillParent(Node l1, Node l2){
	Node new1;
	new1.freq = l1.freq + l2.freq;
	new1.right = &l1;
	new1.left = &l2;

	return new1;
}

void main(){
	int x = 25;
	Node leaf[26];
	leaf[0] = fillLeaf('e',11);
	leaf[1] = fillLeaf('o',9);
	leaf[2] = fillLeaf('t',8);
	leaf[3] = fillLeaf('a',7);
	leaf[4] = fillLeaf('n',7);
	leaf[5] = fillLeaf('i',6);
	leaf[6] = fillLeaf('s',6);
	leaf[7] = fillLeaf('r',6);
	leaf[8] = fillLeaf('h',6);
	leaf[9] = fillLeaf('l',4);
	leaf[10] = fillLeaf('u',4);
	leaf[11] = fillLeaf('d',3);
	leaf[12] = fillLeaf('m',3);
	leaf[13] = fillLeaf('c',2);
	leaf[14] = fillLeaf('f',2);
	leaf[15] = fillLeaf('p',2);
	leaf[16] = fillLeaf('y',2);
	leaf[17] = fillLeaf('g',2);
	leaf[18] = fillLeaf('w',2);
	leaf[19] = fillLeaf('b',2);
	leaf[20] = fillLeaf('v',1);
	leaf[21] = fillLeaf('k',1);
	leaf[22] = fillLeaf('x',1);
	leaf[23] = fillLeaf('j',1);
	leaf[24] = fillLeaf('q',1);
	leaf[25] = fillLeaf('z',1);

	for(int i  = 0 ; i < 26; i++){
		cout << "\nthe value of leaf["<<i<<"] is the letter is "<<leaf[i].letter<< " and the frequency is " <<leaf[i].freq;
	}

	Node l2[13];
	int j = 12;
	for(int i = 0; i < 13; i++){
		l2[j] = fillParent(leaf[x],leaf[x-1]);
		x--;
		x--;
		j--;

	}

	for(int i  = 0 ; i < 13; i++){
		cout << "\nthe freq of parent["<<i<<"] is  "<<l2[i].freq<< " and its right leafs letter is " << l2[i].right->letter;
	}
	//here
	x = 13;

	Node l3[6];
	for(int i = 0; i < 6; i++){

		l3[i] = fillParent(l2[x-1],l2[x-2]);	
		x--;
		x--;


	}
	Node temp[6];
	x = 6;
	for(int i = 0; i < 6; i++){
		j = x -1;
		for(;j < x;){
			temp[i] = l3[j];
			j++;
		}
		x--;

	}

	for(int i = 0; i < 6; i ++){
		l3[i] = temp[i];
	}

	for(int i  = 0 ; i < 6; i++){
		cout << "\nthe freq of parent["<<i<<"] in l3 is  "<<l3[i].freq<< " and its right leafs letter is " << l3[i].right->letter;
	}


	x = 4;
	Node l4[3];
	l4[0].freq = l2[0].freq + l3[5].freq;
	for(int i = 1; i < 3; i++){

		l4[i] = fillParent(l3[x],l3[x-1]);	
		x--;
		x--;


	}

	Node temp2[3];
	x = 3;
	for(int i = 0; i < 3; i++){
		j = x -1;
		for(;j < x;){
			temp2[i] = l4[j];
			j++;
		}
		x--;

	}

	for(int i = 0; i < 6; i ++){
		l4[i] = temp2[i];
	}

	for(int i  = 0 ; i < 3; i++){
		cout << "\nthe freq of parent["<<i<<"] in l4 is  "<<l4[i].freq;
	}

	Node l5[2];
	l5[0].freq = l4[1].freq + l3[0].freq;
	l5[0].right = &l3[0];
	l5[0].left = &l4[2];
	l5[1].freq = l4[2].freq + l4[0].freq;
	l5[1].right = &l4[0];
	l5[1].left = &l4[2];

	for(int i  = 0 ; i < 2; i++){
		cout << "\nthe freq of parent["<<i<<"] in l5 is  "<<l5[i].freq;
	}

	Node root;
	root.freq = l5[0].freq + l5[1].freq;
	root.right = &l5[0];
	root.left = &l5[1];


	cout << " \n The frequency of the root is " << root.freq << "and the rooot to the right is pointing at " << root.right->freq;
}

[raptr_dflo]

A probable cause of problems is certainly in your fillParent() routine:

Node fillParent(Node l1, Node l2){
    Node new1;
    new1.freq = l1.freq + l2.freq;
    new1.right = &l1;
    new1.left = &l2;
 
    return new1;
}

You're passing l1 and l2 "by copy", meaning that whichever two nodes you pass into the function, your program makes two new nodes (called l1 and l2) which are copies of the nodes you provided, but exist only within that specific call to fillParent(). You then create a new node, which points to each of the copies, and return a copy of that new node (which also points to the same two copies), and the original new node is destroyed (which is fine). The problem is that the two argument-copy nodes are also destroyed when the function returns, leaving your returned parent-node copy pointing to garbage. You can neatly avoid most of the unnecessary copying, and resolve your problem at the same time, by passing the arguments "by reference". The only change is in the notation of the argument list, note the added ampersands ('&'):

Node fillParent(Node & l1, Node & l2){
    Node new1;
    new1.freq = l1.freq + l2.freq;
    new1.right = &l1;
    new1.left = &l2;
 
    return new1;
}

In this way, l1 and l2 are referring to the actual nodes you passed in, rather than copies of those nodes, thus the phrase "pass by reference". It is nearly the same as passing pointers to the nodes, and then dereferencing the pointers inside the function.