doing things with binary trees





I've been shaking the bugs out of this program, that would read lines of
text using a binary tree.

The first thing I'd like to do with this tree is print it. I have code for
it here, and it works almost flawlessly. It does, however, print the root
node last. How do I fix it:

// arnold6.c text input using binary tree

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

#define text_length 8192
#define my_file "text43.txt"

int getline(FILE *, char *, int );
struct tnode *add_to_tree( struct tnode *, char * );
void print_tree( struct tnode * );
struct tnode *tree_alloc( void );
char *dupstr( char * );

struct tnode
{
char *text;
int count;
unsigned long lineNumber;
struct tnode *left;
struct tnode *right;
};

int main( void )
{
struct tnode *root_node;
char text[ text_length ];
FILE *fp;
int len;

unsigned long lineNumber = 0;
root_node = NULL;

if ((fp = fopen(my_file, "r")) == NULL )
{
fprintf(stderr, "can't open file\n");
exit(EXIT_FAILURE);
}

while((len = getline(fp, text, text_length)) > 0)
{
++ lineNumber;
//printf("%lu, %s", lineNumber, text);
root_node = add_to_tree( root_node, text);
}

print_tree( root_node );
return 0;
}


/* adds the text onto the tree */
struct tnode *add_to_tree( struct tnode *tree, char *pc )
{
int match;
if( tree == NULL )
{
tree = tree_alloc();
if (tree != NULL)
{
tree->text = dupstr( pc );
tree->count = 1;
tree->left = tree->right = NULL;
}
}
else if( 0 == (match = strcmp( pc, tree->text )) )
{
++tree->count;
}
else if( match > 0 )
{
tree->right = add_to_tree( tree->right, pc );
}
else if( match < 0 )
{
tree->left = add_to_tree( tree->left, pc );
}
return tree;
}


/* prints the tree */
void print_tree( struct tnode *tree )
{
if ( tree != NULL)
{
print_tree(tree->left);
printf("%s -- %4d\n", tree->text, tree->count);
print_tree(tree->right);
}
}

struct tnode *tree_alloc( void )
{
struct tnode *result = malloc(sizeof *result);
if (result == NULL)
{
fputs("Malloc failed", stderr);
exit(EXIT_FAILURE);
}
return result;
}

char *dupstr( char *pc )
{
char *pc2;
pc2 = malloc( strlen(pc) + 1 );
if (pc2 == NULL)
{
fputs("Malloc failed", stderr);
exit(EXIT_FAILURE);
}
strcpy( pc2, pc );
return pc2;
}

/* getline: get line into s, return length */
int getline(FILE *fp, char *s, int lim)
{
char *p;
int c;
p = s;
while (--lim > 0 && (c = getc(fp)) != EOF && c != '\n')
{
*p++ = c;
printf("%p %p\n", p, s);
}
if (c == '\n')
{
*p++ = c;
}
*p = '\0';
return p - s;
}

// gcc arnold6.c -Wall -o arn
// arn >text54.txt

Abridged output:

-- 1012
(which is the sect of the Sadducees,) and were filled with
-- 1
Agrippa, I am accused of the Jews.
-- 1
Alexander, and as many as were of the kindred of the high
-- 1
Alphaeus, and Simon Zelotes, and Judas the brother of James.
-- 1
And he commanded him to be kept in Herod's judgment hall.
-- 1
Aquila and Priscilla had heard, they took him unto them, and
-- 1
Arise, and go into Damascus; and there it shall be told thee
-- 1
Asia,

....

44:028:029 And when he had said these words, the Jews departed, and had
-- 1
44:028:030 And Paul dwelt two whole years in his own hired house, and
-- 1
44:028:031 Preaching the kingdom of God, and teaching those things which
-- 1
Book 44 Acts
-- 1

They are alphabetically-sorted otherwise. The ultimate line of output is
the first line of input.

Thanks for your comment and Cheers,
--
Frank

Whining is anger through a small opening.
~~ Al Franken
.



Relevant Pages

  • Re: doubly-linked list & sorting
    ... have rewritten myself is the getword function. ... ordered manner unless it is a very special hash (e.g. hash(int) = int). ... int getword(char *, int); ... void print_tree(struct tnode *); ...
    (comp.lang.c)
  • doubly-linked list & sorting
    ... int getword(char *, int); ... void print_tree(struct tnode *); ... tree = tree_alloc; ...
    (comp.lang.c)
  • Re: adapting getline
    ... int getline(FILE *, char *, int); ... void print_tree(struct tnode *); ...
    (comp.lang.c)
  • Re: doing things with binary trees
    ... // arnold7.c text input using binary tree ... int getline(FILE *, char *, int); ... void print_tree(struct tnode *); ...
    (comp.programming)
  • Re: starting over
    ... int getline(FILE *, char *, int); ... void print_tree(struct tnode *); ... tree = tree_alloc; ...
    (comp.programming)