LinuxQuestions.org
Go Job Hunting at the LQ Job Marketplace
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 04-24-2006, 03:46 AM   #1
spank
Member
 
Registered: Aug 2003
Location: Romania
Distribution: Ubuntu 6.06
Posts: 278

Rep: Reputation: 30
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!
 
Old 04-24-2006, 05:32 AM   #2
Vagrant
Member
 
Registered: Nov 2001
Posts: 75

Rep: Reputation: 15
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!"
 
Old 04-24-2006, 05:37 AM   #3
spank
Member
 
Registered: Aug 2003
Location: Romania
Distribution: Ubuntu 6.06
Posts: 278

Original Poster
Rep: Reputation: 30
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.
 
Old 04-24-2006, 06:01 AM   #4
Vagrant
Member
 
Registered: Nov 2001
Posts: 75

Rep: Reputation: 15
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);
	}
}
 
Old 04-24-2006, 06:09 AM   #5
spank
Member
 
Registered: Aug 2003
Location: Romania
Distribution: Ubuntu 6.06
Posts: 278

Original Poster
Rep: Reputation: 30
this i don't understand
Code:
		string leftCode = code + "0";
		string rightCode = code + "1";
you have to instances of string code ?
 
Old 04-24-2006, 06:13 AM   #6
Vagrant
Member
 
Registered: Nov 2001
Posts: 75

Rep: Reputation: 15
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);
	}
   }
}
 
Old 04-24-2006, 06:17 AM   #7
spank
Member
 
Registered: Aug 2003
Location: Romania
Distribution: Ubuntu 6.06
Posts: 278

Original Poster
Rep: Reputation: 30
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);
        }
}
 
Old 04-24-2006, 06:22 AM   #8
Vagrant
Member
 
Registered: Nov 2001
Posts: 75

Rep: Reputation: 15
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);
        }
 
Old 04-24-2006, 06:26 AM   #9
spank
Member
 
Registered: Aug 2003
Location: Romania
Distribution: Ubuntu 6.06
Posts: 278

Original Poster
Rep: Reputation: 30
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!
 
Old 04-24-2006, 06:29 AM   #10
Vagrant
Member
 
Registered: Nov 2001
Posts: 75

Rep: Reputation: 15
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.
 
Old 04-24-2006, 06:36 AM   #11
spank
Member
 
Registered: Aug 2003
Location: Romania
Distribution: Ubuntu 6.06
Posts: 278

Original Poster
Rep: Reputation: 30
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.
 
Old 04-24-2006, 06:44 AM   #12
Vagrant
Member
 
Registered: Nov 2001
Posts: 75

Rep: Reputation: 15
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.
 
Old 04-24-2006, 06:51 AM   #13
spank
Member
 
Registered: Aug 2003
Location: Romania
Distribution: Ubuntu 6.06
Posts: 278

Original Poster
Rep: Reputation: 30
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 ?
 
Old 04-24-2006, 07:04 AM   #14
Vagrant
Member
 
Registered: Nov 2001
Posts: 75

Rep: Reputation: 15
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
 
Old 04-24-2006, 07:09 AM   #15
spank
Member
 
Registered: Aug 2003
Location: Romania
Distribution: Ubuntu 6.06
Posts: 278

Original Poster
Rep: Reputation: 30
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...; }
 
  


Reply

Tags
programing


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
representation of binary tree using array sajith Programming 3 10-06-2005 10:59 PM
the bible = the tree of the knowledge of good and evil () Jesus = the tree of life Michael111 General 2 04-14-2004 04:28 PM
Binary search tree insertion in java ksgill Programming 6 02-12-2004 05:11 PM
Printing a binary tree in c? JMC Programming 5 09-26-2003 11:02 AM
need a P-Tree (Patricia Tree) library manaskb Programming 1 11-02-2002 06:15 PM


All times are GMT -5. The time now is 10:11 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration