Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Binary Tree

Reply
Thread Tools

Binary Tree

 
 
Foodbank
Guest
Posts: n/a
 
      10-09-2005
Hi all,

I'm trying to do a binary search and collect some stats from a text
file in order to compare the processing times of this program (binary
searching) versus an old program using linked lists. I'm totally new
to binary searches by the way. Can anyone help me with the commented
sections below? Much of the code such as functions and printfs has
already been completed. Any help is greatly appreciated.

Thanks,
James

Code:
#include <stdio.h>
#include <malloc.h>
struct tnode {			// specify the "shape" of a tnode structure ...
	struct tnode *left;	// the left and right branch pointers
	struct tnode *right;
	int count;		// the word count as before
	char *word;		// a pointer to the word
} *root;			// declare the root pointer variable

struct tnode **tree_search(struct tnode **, char *);
void tree_stats(struct tnode *);
int get_word(char *);

int total_nodes, total_words, high;
struct tnode *most_frequent;

int main(int argc, char *argv[]) {
	struct tnode **tpp;
	char word_buff[100];	// the reusable word buffer
	int i;
	while(get_word(word_buff)) {
		tpp = tree_search(&root, word_buff);
		/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/






	}
	tree_stats(root);
	printf("total_nodes %d\n", total_nodes);
	printf("total_words %d\n", total_words);
	if(most_frequent)
		printf("most frequent word <%s> count is %d\n",
			most_frequent->word, most_frequent->count);
	for(i = 1; i < argc; i++) {
		tpp = tree_search(&root, argv[i]);
		if((*tpp) == NULL)
			printf("%s is NOT in the tree\n", argv[i]);
		else
			printf("<%s> count is %d\n", argv[i], (*tpp)->count);
	}
	return(0);
}

// binary tree search returning a pointer to the pointer leading to a
hit
struct tnode **tree_search(struct tnode **tpp, char *w) {
	/***** CODE TO DO THE BINARY SRCH *****/
	return(tpp);
}

// gather stats to check tree correctness
void tree_stats(struct tnode *tp) {
	/***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/





}

#include <ctype.h>
/* Leave this routine EXACTLY as it stands */
int get_word(char *s) {
	int c;
	do {
		c = getchar();
		if(c == EOF)
			return(0);
	} while(!isalpha(c) && !isdigit(c));
	do {
		if(isupper(c))
			c = tolower(c);
		*s++ = c;
		c = getchar();
	} while(isalpha(c) || isdigit(c));
	*s = 0;
	return(1);
}
 
Reply With Quote
 
 
 
 
kleuske@xs4all.nl
Guest
Posts: n/a
 
      10-09-2005

Foodbank schreef:

> Hi all,
>
> I'm trying to do a binary search and collect some stats from a text
> file in order to compare the processing times of this program (binary
> searching) versus an old program using linked lists.


A "binary search" does not involve any trees, it's a way of searching
through *sorted* sequential lists.

> I'm totally new
> to binary searches by the way. Can anyone help me with the commented
> sections below? Much of the code such as functions and printfs has
> already been completed.


Yes. All but the actual implementation of the tree-building and
searching algo's, which are left to the student. I bet that's what the
teacher gave you as an assignment.

>Any help is greatly appreciated.


>/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/

<snip>
>/***** CODE TO DO THE BINARY SRCH *****/

<snip>
>/***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/


Do your own homework, or at least let us see you trying.

 
Reply With Quote
 
 
 
 
mensanator@aol.com
Guest
Posts: n/a
 
      10-09-2005

Foodbank wrote:
> Hi all,
>
> I'm trying to do a binary search and collect some stats from a text
> file in order to compare the processing times of this program (binary
> searching) versus an old program using linked lists. I'm totally new
> to binary searches by the way. Can anyone help me with the commented
> sections below?


Here's a couple links to how binary trees work. It's about numbers
in a Collatz sequence instead of words but the same principles apply.
In fact, I learned how to do this from the O'Reilly book "Practical
C Programming" where the example processes a list of words. The
solution
I talk about uses a three pointer structure that allows me to create
a binary tree that is simultaneously a linked list. Ignore that third
pointer feature if it's not applicable to your problem.

This is a quickie tutorial on binary trees

<http://groups.google.com/group/Dymanic_Systems/browse_frm/thread/40b6e1f3d696be54/cb42098abc4cf84e?hl=en#cb42098abc4cf84e>

And this is how a binary tree is applicable to the problem of
finding a duplicate number in a Collatz sequence.

<http://groups.google.com/group/Dymanic_Systems/browse_frm/thread/43c11da057cfb30c/6f35e1f30e0a3b43?hl=en#6f35e1f30e0a3b43>

If none of this makes any sense, I can dig up my code examples,
but right now they are coded to use GMP unlimited precision integers
and won't directly plug into your program, but the principles should
apply.

> Much of the code such as functions and printfs has
> already been completed. Any help is greatly appreciated.
>
> Thanks,
> James
>
>
Code:
> #include <stdio.h>
> #include <malloc.h>
> struct tnode {			// specify the "shape" of a tnode structure ...
> 	struct tnode *left;	// the left and right branch pointers
> 	struct tnode *right;
> 	int count;		// the word count as before
> 	char *word;		// a pointer to the word
> } *root;			// declare the root pointer variable
>
> struct tnode **tree_search(struct tnode **, char *);
> void tree_stats(struct tnode *);
> int get_word(char *);
>
> int total_nodes, total_words, high;
> struct tnode *most_frequent;
>
> int main(int argc, char *argv[]) {
> 	struct tnode **tpp;
> 	char word_buff[100];	// the reusable word buffer
> 	int i;
> 	while(get_word(word_buff)) {
> 		tpp = tree_search(&root, word_buff);
> 		/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
>
>
>
>
>
>
> 	}
> 	tree_stats(root);
> 	printf("total_nodes %d\n", total_nodes);
> 	printf("total_words %d\n", total_words);
> 	if(most_frequent)
> 		printf("most frequent word <%s> count is %d\n",
> 			most_frequent->word, most_frequent->count);
> 	for(i = 1; i < argc; i++) {
> 		tpp = tree_search(&root, argv[i]);
> 		if((*tpp) == NULL)
> 			printf("%s is NOT in the tree\n", argv[i]);
> 		else
> 			printf("<%s> count is %d\n", argv[i], (*tpp)->count);
> 	}
> 	return(0);
> }
>
> // binary tree search returning a pointer to the pointer leading to a
> hit
> struct tnode **tree_search(struct tnode **tpp, char *w) {
> 	/***** CODE TO DO THE BINARY SRCH *****/
> 	return(tpp);
> }
>
> // gather stats to check tree correctness
> void tree_stats(struct tnode *tp) {
> 	/***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/
>
>
>
>
>
> }
>
> #include <ctype.h>
> /* Leave this routine EXACTLY as it stands */
> int get_word(char *s) {
> 	int c;
> 	do {
> 		c = getchar();
> 		if(c == EOF)
> 			return(0);
> 	} while(!isalpha(c) && !isdigit(c));
> 	do {
> 		if(isupper(c))
> 			c = tolower(c);
> 		*s++ = c;
> 		c = getchar();
> 	} while(isalpha(c) || isdigit(c));
> 	*s = 0;
> 	return(1);
> }
> 
>


 
Reply With Quote
 
mensanator@aol.com
Guest
Posts: n/a
 
      10-09-2005

http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> Foodbank wrote:
> > Hi all,
> >
> > I'm trying to do a binary search and collect some stats from a text
> > file in order to compare the processing times of this program (binary
> > searching) versus an old program using linked lists. I'm totally new
> > to binary searches by the way. Can anyone help me with the commented
> > sections below?

>
> Here's a couple links to how binary trees work. It's about numbers
> in a Collatz sequence instead of words but the same principles apply.
> In fact, I learned how to do this from the O'Reilly book "Practical
> C Programming" where the example processes a list of words. The
> solution
> I talk about uses a three pointer structure that allows me to create
> a binary tree that is simultaneously a linked list. Ignore that third
> pointer feature if it's not applicable to your problem.
>
> This is a quickie tutorial on binary trees
>
> <http://groups.google.com/group/Dymanic_Systems/browse_frm/thread/40b6e1f3d696be54/cb42098abc4cf84e?hl=en#cb42098abc4cf84e>
>
> And this is how a binary tree is applicable to the problem of
> finding a duplicate number in a Collatz sequence.
>
> <http://groups.google.com/group/Dymanic_Systems/browse_frm/thread/43c11da057cfb30c/6f35e1f30e0a3b43?hl=en#6f35e1f30e0a3b43>


These links take you to the end of the threads. I meant for you to read
the
first message in each thread (the others drift away from the subject
although
you're certainly welcome to read them).


>
> If none of this makes any sense, I can dig up my code examples,
> but right now they are coded to use GMP unlimited precision integers
> and won't directly plug into your program, but the principles should
> apply.
>
> > Much of the code such as functions and printfs has
> > already been completed. Any help is greatly appreciated.
> >
> > Thanks,
> > James
> >
> >
Code:
> > #include <stdio.h>
> > #include <malloc.h>
> > struct tnode {			// specify the "shape" of a tnode structure ...
> > 	struct tnode *left;	// the left and right branch pointers
> > 	struct tnode *right;
> > 	int count;		// the word count as before
> > 	char *word;		// a pointer to the word
> > } *root;			// declare the root pointer variable
> >
> > struct tnode **tree_search(struct tnode **, char *);
> > void tree_stats(struct tnode *);
> > int get_word(char *);
> >
> > int total_nodes, total_words, high;
> > struct tnode *most_frequent;
> >
> > int main(int argc, char *argv[]) {
> > 	struct tnode **tpp;
> > 	char word_buff[100];	// the reusable word buffer
> > 	int i;
> > 	while(get_word(word_buff)) {
> > 		tpp = tree_search(&root, word_buff);
> > 		/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
> >
> >
> >
> >
> >
> >
> > 	}
> > 	tree_stats(root);
> > 	printf("total_nodes %d\n", total_nodes);
> > 	printf("total_words %d\n", total_words);
> > 	if(most_frequent)
> > 		printf("most frequent word <%s> count is %d\n",
> > 			most_frequent->word, most_frequent->count);
> > 	for(i = 1; i < argc; i++) {
> > 		tpp = tree_search(&root, argv[i]);
> > 		if((*tpp) == NULL)
> > 			printf("%s is NOT in the tree\n", argv[i]);
> > 		else
> > 			printf("<%s> count is %d\n", argv[i], (*tpp)->count);
> > 	}
> > 	return(0);
> > }
> >
> > // binary tree search returning a pointer to the pointer leading to a
> > hit
> > struct tnode **tree_search(struct tnode **tpp, char *w) {
> > 	/***** CODE TO DO THE BINARY SRCH *****/
> > 	return(tpp);
> > }
> >
> > // gather stats to check tree correctness
> > void tree_stats(struct tnode *tp) {
> > 	/***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/
> >
> >
> >
> >
> >
> > }
> >
> > #include <ctype.h>
> > /* Leave this routine EXACTLY as it stands */
> > int get_word(char *s) {
> > 	int c;
> > 	do {
> > 		c = getchar();
> > 		if(c == EOF)
> > 			return(0);
> > 	} while(!isalpha(c) && !isdigit(c));
> > 	do {
> > 		if(isupper(c))
> > 			c = tolower(c);
> > 		*s++ = c;
> > 		c = getchar();
> > 	} while(isalpha(c) || isdigit(c));
> > 	*s = 0;
> > 	return(1);
> > }
> > 
> >


 
Reply With Quote
 
Foodbank
Guest
Posts: n/a
 
      10-09-2005
Thanks guys for the links. That made me laugh when you said this was
homework. I wish it were and I was still in school. However, I'm
self-teaching myself C in order to switch from my electrical
engineering based job (my degree in) into more of a programming based
job (I know, I have a long way to go, haha). The program is an
exercise from a book I'm reading.

Thanks,
Jams

 
Reply With Quote
 
Malcolm
Guest
Posts: n/a
 
      10-09-2005

"Foodbank" <(E-Mail Removed)> wrote
> I'm trying to do a binary search and collect some stats from a text
> file in order to compare the processing times of this program (binary
> searching) versus an old program using linked lists. I'm totally new
> to binary searches by the way. Can anyone help me with the commented
> sections below? Much of the code such as functions and printfs has
> already been completed. Any help is greatly appreciated.
>

The idea of a binary search is this.

We have a telephone directory, and want to find an arbitrary name - Gubbins.
Open the directory in the middle. The middle entry will be a name like
"Marks". If it is equal to "Gubbins" you have found your entry, if not, you
know the name must be somewhere between the start of the directory and
"Marks". Now go a quarter way through. This name is "Henry". Still above
"Gubbins", so we know "Gubbins" is in the top quarter. When we check an
eighth of the way through, we find "Evans". So Gubbins is in the second
eighth of the directory. Split on the third sixteenth and you get "Groves".
Gubbins is in the fourth sixteenth, between "Groves" and "Henry". Continue
doing this until you have narrowed to a single entry.

You will see that you eliminate half the possibilities each time, so you
need log2(N) operations to complete the search. This is much faster than
going through the directory sequentially.

Unfortunately this algorithm only works if the directory entries are held in
a sorted array. If we want to insert and delete entries, we have to move the
array about to keep it sorted, which is expensive.

The solution is to use a tree structure. We select an arbitrary entry about
halfway along as the root. All the entries lower than it go in the left
sub-tree, all the entries higher go in the right sub-tree. leaves have null
children. We can easily add new members by growing new leaves, without
rebuilding the whole tree. (The tree doesn't have to be perfectly balanced
for the algorithm to work in reasonable time. Keeping the tree balanced is a
whole new story we won't go into).

The first thing to do is to write the routine that builds the tree. The
first word you encounter goes in the root, the second becomes the right or
the left leaf, and you just continue until you run out of leaves.
Test the tree on a tiny dataset with only half a dozen words, and print it
out so that you can see it is correct.

Then write the function to search the tree, starting at the top and going
down until it either hits a match or encounters a null pointer indicating it
has fallen off a leaf.




 
Reply With Quote
 
Foodbank
Guest
Posts: n/a
 
      10-11-2005
Hi,

Am I on the right path in the section of the code that adds new nodes?
I'm not finished, but trying to make an attempt. It's under the
/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/ section. I'm
pretty sure that it's supposed to check if it's null and if so,
allocates memory for a new node. Syntax is probably wrong, but was
hoping for some input.

Thanks,
James

[code]
#include <stdio.h>
#include <malloc.h>
struct tnode { // specify the "shape" of a tnode
structure ...
struct tnode *left; // the left and right branch pointers
struct tnode *right;
int count; // the word count as before
char *word; // a pointer to the word

} *root; // declare the root pointer variable

struct tnode **tree_search(struct tnode **, char *);
void tree_stats(struct tnode *);
int get_word(char *);

int total_nodes, total_words, high;
struct tnode *most_frequent;


int main(int argc, char *argv[]) {
struct tnode **tpp;
char word_buff[100]; // the reusable word buffer
int i;
while(get_word(word_buff)) {
tpp = tree_search(&root, word_buff);
/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
///new code below here
if(root==NULL)
if(*tpp==NULL){
tpp=malloc(sizeof(struct tnode));
tpp->word = strdup(word_buff);
tpp->*left = NULL;
tpp->*right = NULL;
}
else statement here if there's a node there, increments count I
think, not sure which variables to use

}
[code]

 
Reply With Quote
 
mensanator@aol.com
Guest
Posts: n/a
 
      10-11-2005
Foodbank wrote:
> Hi,
>
> Am I on the right path in the section of the code that adds new nodes?
> I'm not finished, but trying to make an attempt. It's under the
> /****CODE TO ADD NEW NODES AND COUNT REPEATS *****/ section. I'm
> pretty sure that it's supposed to check if it's null and if so,
> allocates memory for a new node. Syntax is probably wrong, but was
> hoping for some input.


I've include my version of the example binary tree program.
It simply builds a tree from the command line arguments.

A key difference is a recursive function to enter a word
onto the tree. It starts at the root and follows left/right
pointers until it either finds the word already on the tree
or finds a NULL. Calling enter() with a NULL will add a node
with count=1 since adding a node means this is the first
occurence.

When the word is found to be already on the tree, we just need
to increment the count.

Also in the program are a pair of print routines, one to print
all the words in the tree with their frequency and another
that shows how the path through the binary tree.

And you will, of course, want to add a routine to free the
allocated memory.

Sample output:

$ ./a the ice was here the ice was there the ice was all around
it cracked and groaned and shrieked and howled like noises in a
swound

a (1) all (1) and (3) around (1) cracked (1) groaned (1)
here (1) howled (1) ice (3) in (1) it (1) like (1) noises (1)
shrieked (1) swound (1) the (3) there (1) was (3)

L L L L L [a - 1]
R U [all - 1]
R L L [and - 3]
R U [around - 1]
R L [cracked - 1]
R L [groaned - 1]
R U U U U [here - 1]
R L [howled - 1]
R U U [ice - 3]
R L L [in - 1]
R U [it - 1]
R L L [like - 1]
R L [noises - 1]
R U U [shrieked - 1]
R L [swound - 1]
R U U U U [the - 3]
R L L [there - 1]
R U [was - 3]
R U U

>
> Thanks,
> James
>
> [code]
> #include <stdio.h>
> #include <malloc.h>
> struct tnode { // specify the "shape" of a tnode
> structure ...
> struct tnode *left; // the left and right branch pointers
> struct tnode *right;
> int count; // the word count as before
> char *word; // a pointer to the word
>
> } *root; // declare the root pointer variable
>
> struct tnode **tree_search(struct tnode **, char *);
> void tree_stats(struct tnode *);
> int get_word(char *);
>
> int total_nodes, total_words, high;
> struct tnode *most_frequent;
>
>
> int main(int argc, char *argv[]) {
> struct tnode **tpp;
> char word_buff[100]; // the reusable word buffer
> int i;
> while(get_word(word_buff)) {
> tpp = tree_search(&root, word_buff);
> /****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
> ///new code below here
> if(root==NULL)
> if(*tpp==NULL){
> tpp=malloc(sizeof(struct tnode));
> tpp->word = strdup(word_buff);
> tpp->*left = NULL;
> tpp->*right = NULL;
> }
> else statement here if there's a node there, increments count I
> think, not sure which variables to use
>
> }
> [code]





#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

// gcc -g -I. c/foodbank.c

struct node {
struct node *left; // tree to the left
struct node *right; // tree to the right
unsigned int count; // # of occurences...
char *word; // ...of this word
};

static struct node *root = NULL;

void memory_error(void)
{
fprintf(stderr, "Error:Out of memory\n");
exit(;
}

char *save_w(char *string) // copy string to heap
{
char *new_string;
new_string = malloc((unsigned) (strlen(string)+1));
if (new_string == NULL)
memory_error();
strcpy(new_string,string);
return (new_string);
}

void enter(struct node **node, char *word)
{
char *save_w();
int comp;

if ((*node) == NULL)
{
(*node) = malloc(sizeof(struct node));
if ((*node) == NULL)
memory_error();
(*node)->left = NULL;
(*node)->right = NULL;
(*node)->count = 1; // new node = first occurence
(*node)->word = save_w(word); // of this word
return;
}
comp = strcmp((*node)->word,word);
if (comp==0 )
{
(*node)->count++; // word already in tree
return;
}
if (comp<0)
enter(&(*node)->right,word); // recursively try to enter word
else // until a NULL is found
enter(&(*node)->left,word);
}

void print_tree(struct node *top)
{
if (top == NULL)
return;
print_tree(top->left);
printf("%s (%d) ", top->word,top->count);
print_tree(top->right);
}

void print_tree_debug(struct node *top)
{
if (top == NULL)
return;
printf("L "); // go left
print_tree_debug(top->left);
printf("[%s - %d]\n", top->word,top->count);
printf("R "); // go right
print_tree_debug(top->right);
printf("U "); // go up
}

int main(int argc, char *argv[])
{
unsigned int i;

for (i=1; i<argc; i++)
enter(&root,argv[i]);

printf("\n");
print_tree(root);
printf("\n");

printf("\n");
print_tree_debug(root);
printf("\n");

return (0);
}

 
Reply With Quote
 
Barry Schwarz
Guest
Posts: n/a
 
      10-12-2005
On 11 Oct 2005 15:26:31 -0700, "(E-Mail Removed)"
<(E-Mail Removed)> wrote:

snip

>I've include my version of the example binary tree program.
>It simply builds a tree from the command line arguments.
>
>A key difference is a recursive function to enter a word
>onto the tree. It starts at the root and follows left/right
>pointers until it either finds the word already on the tree
>or finds a NULL. Calling enter() with a NULL will add a node
>with count=1 since adding a node means this is the first
>occurence.
>
>When the word is found to be already on the tree, we just need
>to increment the count.
>
>Also in the program are a pair of print routines, one to print
>all the words in the tree with their frequency and another
>that shows how the path through the binary tree.
>
>And you will, of course, want to add a routine to free the
>allocated memory.
>

snip

>> [code]

>
>
>
>
>#include <stdio.h>
>#include <ctype.h>
>#include <string.h>
>#include <stdlib.h>
>
>// gcc -g -I. c/foodbank.c
>
>struct node {
> struct node *left; // tree to the left
> struct node *right; // tree to the right
> unsigned int count; // # of occurences...
> char *word; // ...of this word
>};
>
>static struct node *root = NULL;


Since you pass root to every function that needs it, there is no need
for it to be at file scope. This will prevent an unintended function
from modifying it.

>
>void memory_error(void)
>{
> fprintf(stderr, "Error:Out of memory\n");
> exit(;


EXIT_FAILURE would be more portable than 8.
>}
>
>char *save_w(char *string) // copy string to heap
>{
> char *new_string;
> new_string = malloc((unsigned) (strlen(string)+1));
> if (new_string == NULL)
> memory_error();
> strcpy(new_string,string);
> return (new_string);
>}
>
>void enter(struct node **node, char *word)
>{
> char *save_w();


Marginally incorrect and error prone. save_w was defined above. That
will serve as the prototype of any subsequent calls to the function.
If you are going to repeat a declaration, repeat it exactly.

> int comp;
>
> if ((*node) == NULL)
> {
> (*node) = malloc(sizeof(struct node));
> if ((*node) == NULL)
> memory_error();
> (*node)->left = NULL;
> (*node)->right = NULL;
> (*node)->count = 1; // new node = first occurence
> (*node)->word = save_w(word); // of this word
> return;
> }
> comp = strcmp((*node)->word,word);
> if (comp==0 )
> {
> (*node)->count++; // word already in tree
> return;
> }
> if (comp<0)
> enter(&(*node)->right,word); // recursively try to enter word
> else // until a NULL is found
> enter(&(*node)->left,word);
>}
>
>void print_tree(struct node *top)
>{
> if (top == NULL)
> return;
> print_tree(top->left);
> printf("%s (%d) ", top->word,top->count);
> print_tree(top->right);
>}
>
>void print_tree_debug(struct node *top)
>{
> if (top == NULL)
> return;
> printf("L "); // go left
> print_tree_debug(top->left);
> printf("[%s - %d]\n", top->word,top->count);
> printf("R "); // go right
> print_tree_debug(top->right);
> printf("U "); // go up
>}
>
>int main(int argc, char *argv[])
>{
> unsigned int i;
>
> for (i=1; i<argc; i++)
> enter(&root,argv[i]);
>
> printf("\n");
> print_tree(root);
> printf("\n");
>
> printf("\n");
> print_tree_debug(root);
> printf("\n");
>
> return (0);
>}



<<Remove the del for email>>
 
Reply With Quote
 
mensanator@aol.com
Guest
Posts: n/a
 
      10-12-2005

Barry Schwarz wrote:
> On 11 Oct 2005 15:26:31 -0700, "(E-Mail Removed)"
> <(E-Mail Removed)> wrote:
>
> snip
>
> >I've include my version of the example binary tree program.
> >It simply builds a tree from the command line arguments.
> >
> >A key difference is a recursive function to enter a word
> >onto the tree. It starts at the root and follows left/right
> >pointers until it either finds the word already on the tree
> >or finds a NULL. Calling enter() with a NULL will add a node
> >with count=1 since adding a node means this is the first
> >occurence.
> >
> >When the word is found to be already on the tree, we just need
> >to increment the count.
> >
> >Also in the program are a pair of print routines, one to print
> >all the words in the tree with their frequency and another
> >that shows how the path through the binary tree.
> >
> >And you will, of course, want to add a routine to free the
> >allocated memory.
> >

> snip
>
> >> [code]

> >
> >
> >
> >
> >#include <stdio.h>
> >#include <ctype.h>
> >#include <string.h>
> >#include <stdlib.h>
> >
> >// gcc -g -I. c/foodbank.c
> >
> >struct node {
> > struct node *left; // tree to the left
> > struct node *right; // tree to the right
> > unsigned int count; // # of occurences...
> > char *word; // ...of this word
> >};
> >
> >static struct node *root = NULL;

>
> Since you pass root to every function that needs it, there is no need
> for it to be at file scope. This will prevent an unintended function
> from modifying it.


Where does it go? FWIW, I copied (and modified) this code out
of the O'Reilly book "Practical C Programming" by Steve Oualline.
I don't know enough to make a mistake that sophisticated.

>
> >
> >void memory_error(void)
> >{
> > fprintf(stderr, "Error:Out of memory\n");
> > exit(;

>
> EXIT_FAILURE would be more portable than 8.


Ditto, didn't know there was such a constant.

> >}
> >
> >char *save_w(char *string) // copy string to heap
> >{
> > char *new_string;
> > new_string = malloc((unsigned) (strlen(string)+1));
> > if (new_string == NULL)
> > memory_error();
> > strcpy(new_string,string);
> > return (new_string);
> >}
> >
> >void enter(struct node **node, char *word)
> >{
> > char *save_w();

>
> Marginally incorrect and error prone. save_w was defined above. That
> will serve as the prototype of any subsequent calls to the function.
> If you are going to repeat a declaration, repeat it exactly.


That one's partially my fault. The prototype is in the book,
but it got inexplicably changed when I was modifying it.

Thanks for pointing those out. I'm not a C programmer but
occaisionally need to create C programs. I'm completely
dependant on examples from books. Good to know that even
the books aren't perfect.

>
> > int comp;
> >
> > if ((*node) == NULL)
> > {
> > (*node) = malloc(sizeof(struct node));
> > if ((*node) == NULL)
> > memory_error();
> > (*node)->left = NULL;
> > (*node)->right = NULL;
> > (*node)->count = 1; // new node = first occurence
> > (*node)->word = save_w(word); // of this word
> > return;
> > }
> > comp = strcmp((*node)->word,word);
> > if (comp==0 )
> > {
> > (*node)->count++; // word already in tree
> > return;
> > }
> > if (comp<0)
> > enter(&(*node)->right,word); // recursively try to enter word
> > else // until a NULL is found
> > enter(&(*node)->left,word);
> >}
> >
> >void print_tree(struct node *top)
> >{
> > if (top == NULL)
> > return;
> > print_tree(top->left);
> > printf("%s (%d) ", top->word,top->count);
> > print_tree(top->right);
> >}
> >
> >void print_tree_debug(struct node *top)
> >{
> > if (top == NULL)
> > return;
> > printf("L "); // go left
> > print_tree_debug(top->left);
> > printf("[%s - %d]\n", top->word,top->count);
> > printf("R "); // go right
> > print_tree_debug(top->right);
> > printf("U "); // go up
> >}
> >
> >int main(int argc, char *argv[])
> >{
> > unsigned int i;
> >
> > for (i=1; i<argc; i++)
> > enter(&root,argv[i]);
> >
> > printf("\n");
> > print_tree(root);
> > printf("\n");
> >
> > printf("\n");
> > print_tree_debug(root);
> > printf("\n");
> >
> > return (0);
> >}

>
>
> <<Remove the del for email>>


 
Reply With Quote
 
 
 
Reply

Thread Tools

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 On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Binary tree search vs Binary search Bogdan C Programming 22 10-21-2010 09:46 PM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 2 10-31-2007 02:58 AM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 1 10-30-2007 11:01 PM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 4 10-30-2007 08:21 PM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM



Advertisments