Binary tree in C

spank · 04-24-2006, 04:46 AM

i want to obtain the binary code of all the leafes of a bin tree. have any ideea on how to do that?

i code 0 for left and 1 of right.
Thank you!

Vagrant · 04-24-2006, 06:32 AM

Quote:

Originally Posted by spank

i want to obtain the binary code of all the leafes of a bin tree. have any ideea on how to do that?

i code 0 for left and 1 of right.
Thank you!

This sounds like homework. You need to know 3 things: recursion, how to traverse a tree, and that you need to maintain the proper string through each recursive call.

Look up "tree traversal." I'll give you hint, if you write a lot of code for this then you're wrong. The root node is a special case, every other node you are building a string which will be printed when you hit a leaf. Oh, and remember "recursion!"

spank · 04-24-2006, 06:37 AM

i'm trying to implement the huffman compresion algorithm... and i don't know how to obtain the binary code for each character. And no.. the standart traversals of a tree don't work in this case.

Vagrant · 04-24-2006, 07:01 AM

I've written Huffman, and it really is a basic traversal.

With this, you should be able to flesh it out.
pseudo-code:

Code:

void buildEncode(Node n, string code)
{
	if(isLeaf(n)
	{
		print(code);
	}
	else
	{
		string leftCode = code + "0";
		string rightCode = code + "1";

		buildEncode(n.getLeft(), leftCode);
		buildEncode(n.getRight(), rightCode);
	}
}

spank · 04-24-2006, 07:09 AM

this i don't understand

Code:

		string leftCode = code + "0";
		string rightCode = code + "1";

you have to instances of string code ?

Vagrant · 04-24-2006, 07:13 AM

This bit here:

The function, buildEncode, takes in the parameter "code"

void buildEncode(Node n, string code)

So, "code" is local to the function, only one instance. That bit is very much like C. That variable symbolizes the "huffman code so far." If you get to those statements, you know you aren't on a leaf, therefore you will need to visit at least one more node. Actually, there is one more case, to keep you from spinning on it, I'll add it. Check for null:

Code:

void buildEncode(Node n, string code)
{
   if(n != NULL)
   {
	if(isLeaf(n)
	{
		print(code);
	}
	else
	{
		string leftCode = code + "0";
		string rightCode = code + "1";

		buildEncode(n.getLeft(), leftCode);
		buildEncode(n.getRight(), rightCode);
	}
   }
}

spank · 04-24-2006, 07:17 AM

you mean something like this?

Code:

void preordine(tree a,char bin[100])
{
        char s[100],d[100];
        if((a->leg[0]==NULL)&&(a->leg[1]==NULL))
        {
                puts(bin);
        }
        else
        {
                strcat(s,"0");
                strcat(d,"1");
                preordine(a->leg[0],s);
                preordine(a->leg[1],d);
        }
}

Vagrant · 04-24-2006, 07:22 AM

Quote:

Originally Posted by spank

you mean something like this?

Code:

void preordine(tree a,char bin[100])
{
        char s[100],d[100];
        if((a->leg[0]==NULL)&&(a->leg[1]==NULL))
        {
                puts(bin);
        }
        else
        {
                strcat(s,"0");
                strcat(d,"1");
                preordine(a->leg[0],s);
                preordine(a->leg[1],d);
        }
}

Well, add the NULL check I made in the last post. If this code:

if((a->leg[0]==NULL)&&(a->leg[1]==NULL))

is equivalent to:

if(isLeaf(n))

Then this is close. However, you have a mistake. You must include "bin" in both places. You should have something closer to

Code:

        else
        {
                strcpy(s,bin);
                strcpy(d, bin);

                strcat(s,"0");
                strcat(d,"1");
                preordine(a->leg[0],s);
                preordine(a->leg[1],d);
        }

spank · 04-24-2006, 07:26 AM

Code:

void preordine(tree a,char bin[100])
{
        char s[100],d[100];
        if((a->leg[0]==NULL)&&(a->leg[1]==NULL))
        {
                printf("%lf\n",a->prob);
                puts(bin);
        }
        else
        {
                strcpy(s,bin);
                strcpy(d,bin);
                strcat(s,"0");
                strcat(d,"1");
                preordine(a->leg[0],s);
                preordine(a->leg[1],d);
        }
}

great.... i owe you a big blonde beer

Cheers!

Vagrant · 04-24-2006, 07:29 AM

No problem. =)

Again, its kind of early, but I think you need to make sure "a" is not null before you make those two checks.

spank · 04-24-2006, 07:36 AM

the tree will always have an element in it. and when it is built i use calloc that initializes all poiners with null. so i think it will never be null.

Vagrant · 04-24-2006, 07:44 AM

Right, the only problem would be if a parent had only one child, say a left child, then after this line:

preordine(a->leg[1],d);

When the preordine from this call runs, "a" will be null and you will get a seg-fault. Without the null check on "a," the code will only work if all parents have exactly two children.

spank · 04-24-2006, 07:51 AM

uuuuuf.... right again.

now something a little offtopic... my program only works on text files. when you did the huffman how did you read the file ?

Vagrant · 04-24-2006, 08:04 AM

Well, just use the standard mechanisms. The C++ way would be to use fstream, like so:

Code:

void buildFreqTable(char *input)
{
        char symbol;
        ifstream infile;


        infile.open(input, ios::binary);


        while(infile.get(symbol))
        {
             addToFreqTable(symbol);
        }


        infile.close();
}

If you need to do it in C, its the same basic idea, just use fopen/fgetc, this is a quick guide:

http://www.cprogramming.com/tutorial/cfileio.html

spank · 04-24-2006, 08:09 AM

yes that is what i used but it doesn't work with binary files. for reading i used:

Code:

FILE  *f=fopen("fis.in","rb");
char c;
while((c=fgetc(f)))!=EOF) { reading...; }