Thread: K&R 6-4 : won't read Struct *

From K&R's chapter6, #4, I have a Struct tnode "root" full of words, sorted alphabetically, with word-count for each one. The task was to print the list of words, but sorted by decreasing word count. I attempted reading all the nodes from the struct into an array, then was going to sort the array, but couldn't get it to work.

Now I am trying to use the (first) struct 'root', to create a new structure 'root3'. This new struct is comparing the Count of each word, so it builds the structure naturally by decreasing-word-count. Then the original 'treeprint' function can print it. It compiles ok (with a warning about *treeread not always returning a value), but then after input does nothing and eventually times out.

I highlighted where it is getting stuck in an infinite loop.

Can anyone catch what the problem is?

Code:

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

#define MAXWORD 100

struct tnode *addtree(struct tnode *, char *);
struct tnode *addtree2(struct tnode *, struct tnode *);
void treeprint(struct tnode *);
struct tnode *treeread(struct tnode *);
int getword(char *, int);

struct tnode { /*the tree node:*/
	char *word; /*points to the text*/
	int count; /*number of occurrences*/
	struct tnode *left; /*left child*/
	struct tnode *right; /*right child*/
};

/*word frequency count*/
main (int argc, char *argv[]) {
	struct tnode *root=NULL, *root2=NULL, *root3=NULL;
	char word[MAXWORD];
	int i;

	while (getword(word,MAXWORD) != '>') {
		if (isalpha(word[0]))
			root = addtree(root,word);
	}
	while ((root2=treeread(root))!= NULL) {
		if (isalpha(word[0]))
			root3 = addtree2(root3,root2);
	}
	treeprint(root3);
	return 0;
}

struct tnode *talloc(void);
char *strdup(char *);

/* addtree: add a node with w, at or below p */
struct tnode *addtree(struct tnode *p, char *w) {
	int cond;

	if (p==NULL) { /*a new word has arrived; make a new node */
		p=talloc();
		p->word=strdup(w);/*string duplicate*/
		p->count=1;
		p->left = p->right = NULL;
	} else if ((cond = strcmp(w, p->word))==0)
		p->count++; /*repeated word*/
	else if (cond<0) /*less than, into left subtree*/
		p->left=addtree(p->left,w);
	else
		p->right=addtree(p->right,w);
	return p;
}

/* addtree2: add a node with w, at or below p; comparing word-count */
struct tnode *addtree2(struct tnode *p, struct tnode *w) { printf("hello");
	if (p==NULL) { /*a new word has arrived; make a new node */
		p=talloc();
		p->word=w->word;
		p->count=1;
		p->left = p->right = NULL;
	} else if (w->count <= p->count) /*less than or =, into left subtree*/
		p->left=addtree2(p->left,w);
	else
		p->right=addtree2(p->right,w);
	return p;
}

/*treeprint: alphabetical order print of tree p*/
void treeprint(struct tnode *p) {
	if (p!=NULL) {
		treeprint(p->left);
		printf("%4d %s\n", p->count,p->word);
		treeprint(p->right);
	}
}

struct tnode *treeread(struct tnode *p) {/*here it gets stuck in loop*/	if (p!=NULL) {
		treeread(p->left);
		treeread(p->right);
		return p;
	}
}

/*talloc: make a tnode*/
struct tnode *talloc(void) {
	return (struct tnode *) malloc(sizeof(struct tnode));
}

char *strdup(char *s) { /*make a duplicate of s*/
	char *p;
	p=(char *) malloc(strlen(s)+1); /*+1 for '\0'*/
	if (p != NULL)
		strcpy(p,s);
	return p;
}

/*getword: get next word or character from input*/
int getword(char *word, int lim) {
	int c,getch(void);
	void ungetch(int);
	char *w=word;

	while (isspace(c=getch()))
		;
	if (c!=EOF)
		*w++=c;
	if (!isalpha(c)){
		*w='\0';
		return c;
	}
	for (;--lim>0;w++) {
		if (!isalnum(*w=getch())) {
			ungetch(*w);
			break;
		}
	}
	*w = '\0';
	return word[0];
}

#define BUFSIZE 100

char buf[BUFSIZE]; /*buffer for ungetch*/
int bufp=0;        /*next free position in buf*/

int getch(void) /*get a (possibly pushed-back) character */
{
	return (bufp>0) ? buf[--bufp] : getchar();
}

void ungetch(int c)
{
	if (bufp>=BUFSIZE)
		printf("ungetch:too many characters\n");
	else
		buf[bufp++]=c;
}

Code:

struct tnode *treeread(struct tnode *p) {/*here it gets stuck in loop*/	if (p!=NULL) {
		treeread(p->left);
		treeread(p->right);
		return p;
	}
}

I'm surprised your compiler didn't warn you that it is possible to reach the end of this function without returning anything. I don't think that's your problem, but maybe move the return p outside of the if block...

Code:

struct tnode *treeread(struct tnode *p) {/*here it gets stuck in loop*/	
        if (p) {
		treeread(p->left);
		treeread(p->right);
	}
	return p;
}