A binary tree and its pointers ... (PLEASE help)

Question

A binary tree and its pointers ... (PLEASE help)

ankan (Programmer)

(OP)

28 Jul 01 12:11

PLEASE help in anyway you can. I've got fed up with trying to solve this.

Lets get to the point directly...
A simple binary tree...
struct tnode {
    char **word; /* this stores the different words */
    int count;   /* this keeps the count */
    struct tnode *left;
    struct tnode *right;
};

A simpler objective... to store in the above tree and print out each group of words from an input buffer that have the first few (how many? given by the variable 'till') characters identical, in alphabetical order.
The words are sent to the function addtree:

struct tnode *addtree(struct tnode *p, char *w, int till)
{
    int cond;
    if(p==NULL) {  /* found new */
        p = (struct tnode *) malloc(sizeof(struct tnode));
        p->count = 1;
        p->word[(p->count)-1] = strdup(w);
        p->left = p->right = NULL;
    } else if((cond = strncmp(w, p->word[0], till)) == 0) { /* found a match */
        p->count++;
        p->word[(p->count)-1] = strdup(w);
        printf("Added to old... new: %s\n", w);
    } else if(cond < 0)
        p->left = addtree(p->left, w, till);
    else
        p->right = addtree(p->right, w, till);
return p;
}

The main fiunction ...
int main()
{
    struct tnode* root;
    int till = 6;
/* ... */
/* --------- snip ------ */
    root = NULL;
    while (getw(word, in) != EOF) /* getw() gets the next word from the input stream 'in' */
        if(isalpha(word[0]))
            root = addtree(root, word, till);
    treeprint(root);  /* a function traversing the binary tree for printing */
/* --------- snip ------ */
/* ... */
}

The Problem ... Its not running correctly. Sometimes it prints out only the last word. Sometimes the "This program has performed an illegal operation..." message crops up. And sometimes its not running at all!! There maybe a problem with the pointers. But where??
On stepping through with the Debugger it gave "Stopped at exception throw" error. And also the root->word (in main) gets changed with every call to the recursive function (although the address of root does not change, it should not anyway). But it seems (after much tracing through the code with the debugger) that the malloc function (bolded) in the recursive function gives the same address to p in each subsequent recursive call!!

Where did I go wrong? Give me a hint but please reply.
Can you help?? Please.

Note: I posted the above query in the C forum but since there was absolutely no response, I'm trying here.

Waiting.
Ankan.

Please do correct me if I am wrong.

Zyrenthian (Programmer) · Answer 1 · 2001-07-30 13:52:18

the 2d pointer in the struct is your problem. You define no dimentions so only one pointer to a string exists. You would have to do somethng along the lines of

struct tnode{
char* word[MAX_WORDS];
...
}

and on the insert

if p->count-1<MAX_WORDS // dont add it

Matt

ankan (Programmer) · Answer 2 · 2001-07-30 15:55:11

Thankyou very much, Zyrenthian. You were right. The problem was that I did not allocate space for the whole thing first (how darn stupid of me!).
I assume that you meant "if p->count-1 > MAX_WORDS // dont add it".
However, I did not change the structure,
struct tnode{
  char **word;
...
}
since I wanted to allocate memory dynamically.

Here's what I did ultimately ...

struct tnode *addtree(struct tnode *p, char *w, int till)
{
    int cond;
    if(p == NULL) {
        if( (p = (struct tnode *) malloc(sizeof(struct tnode))) == NULL)
            return NULL;
        p->count = 1;
        if( (p->word = realloc(p->word, sizeof(p->word)+strlen(w))) == NULL) {
            free(p);
            return NULL;
        }
        if( (p->word[p->count - 1] = strdup(w)) == NULL) {
            free(p);
            return NULL;
        }
        strcpy(p->word[p->count - 1], w);
        p->left = p->right = NULL;
    }
    else if((cond = strncmp(w, p->word[0], till)) == 0) {
        p->count++;
        if( (p->word = realloc(p->word, sizeof(p->word)+strlen(w))) == NULL) {
            free(p);
            return NULL;
        }
        if( (p->word[p->count - 1] = strdup(w)) == NULL) {
            free(p);
            return NULL;
        }
        strcpy(p->word[p->count - 1], w);
    }
    else if(cond < 0)
        p->left = addtree(p->left, w, till);
    else
        p->right = addtree(p->right, w, till);
return p;
}

It seems to be working now (although, as yet i have checked only on small and simple inputs).

Bye.
Ankan.

Please do correct me if I am wrong.

ankan (Programmer) · Answer 3 · 2001-07-31 10:17:55

Make that
...
if( (p->word = realloc(p->word, sizeof(p->word)+strlen(w)+1)) == NULL) {
...

(the classical forgetting of the '\0'), and other small changes not worth mentioning.

Bye.
Ankan.

Please do correct me if I am wrong.

Come Join Us!

Posting Guidelines

Jobs

A binary tree and its pointers ... (PLEASE help)