LinuxQuestions.org
Page 1 of 2 1 2
Show 50 post(s) from this thread on one page

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   Binary tree in C (https://www.linuxquestions.org/questions/programming-9/binary-tree-in-c-438254/)

spank 04-24-2006 03:46 AM
Binary tree in C
 
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 05: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 05: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 06: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 06: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 06: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 06: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 06: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 06: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 06: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 06: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 06: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 06: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 07: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 07: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...; }


All times are GMT -5. The time now is 01:41 AM.
Page 1 of 2 1 2
Show 50 post(s) from this thread on one page