how to implement general (each node) tree with c program

**Nepomuk** · May 28 '13, 11:10 AM

Hi samiman and welcome to bytes.com!

According to our posting guidelines, we will not do your homework for you. We will however gladly help you solve the homework yourself if you show us what you've done so far.

To get started with the task I would ask myself how a tree works and which elements from the C language could represent which parts of that structure. Maybe have another look at the material from the course on C you're obviously doing. You might even have similar examples - lists are commonly shown and are very similar to trees.

**samiman** · May 29 '13, 09:23 PM

this was what i have done but it is not working

Code:

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define SIZE 9

typedef struct treeNode
{
        int item;
        struct treeNode *left;
        struct treeNode *mid;
        struct treeNode *right;

}treeNode;


typedef int (*comparer)(int, int);

int compare(int a,int b)
{
    if(a < b)
        return 1;
    if(b<a<=b+5)
        return 2;
    if (a>b+5)
        return 3;
    return 0;
}
treeNode* create_node(int value)
{
    treeNode *new_node = (treeNode*)malloc(sizeof(treeNode));
    if(new_node == NULL)
    {
        fprintf (stderr, "Out of memory!!! (create_node)\n");
        exit(1);
    }
    new_node->item = value;

    new_node->left = NULL;
    new_node->mid = NULL;
    new_node->right = NULL;
    return new_node;
}
typedef int (*comparer)(int, int);
void insertNode(treeNode *root,comparer compare,int item)
{
if (root == NULL){
       root = create_node(item);
    }

   else{
        int is_left = 0;
        int is_mid = 0;
        int is_right = 0;
        int r;
        treeNode* cursor = root;
        treeNode* prev = NULL;
        while(cursor != NULL){
            r = compare(item,cursor->item);
            prev = cursor;
            if (r==1){
                is_left = 1;
                cursor = cursor->left;
            }else if(r==2){
                is_mid = 1;
                cursor = cursor->mid;
            }else if(r==3){
                is_right = 1;
                cursor = cursor->right;
            }
            }
        if(is_left)
           prev->left = create_node(item);
         else if(is_mid)
           prev->mid = create_node(item);
         else if(is_right)
           prev->right = create_node(item);

    else{
        printf("duplicate values are not allowed!");
    }
    return root;
}
treeNode * search(treeNode *root,const int item,comparer compare)
{
 if (root == NULL)
    return NULL;

 int r;
 treeNode* cursor = root;
 while (cursor!=NULL){
    r=compare(item,cursor->item);
    if(r==1)
        cursor = cursor->left;
    else if(r == 2)
        cursor = cursor->mid;
    else if(r == 3)
        cursor = cursor->right;
 }
 return cursor;

}
              //delete a node
treeNode* delete_node(treeNode* root,int item,comparer compare)
{
    if(root==NULL)
        return NULL;
    treeNode *cursor;
    int r = compare(item,root->item);
    if(r==1)
        root->left = delete_node(root->left,item,compare);
    else if(r==2)
        root->mid = delete_node(root->mid,item,compare);
    else if(r==3)
        root->right = delete_node(root->right,item,compare);
    else{
        if(root->left == NULL && root->mid == NULL)
            {
            cursor = root->right;
            free(root);
            root = cursor;
            }
        else if(root->left == NULL && root->right==NULL){
            cursor = root->mid;
            free(root);
            root = cursor;
        }
        else if(root->right == NULL && root->mid == NULL){
            cursor = root->left;
            free(root);
            root = cursor;
        }

    }

  return root;
}
void dispose(treeNode* root)
{
    if(root != NULL)
    {
        dispose(root->left);
        dispose(root->mid);
        dispose(root->right);
        free(root);
    }
}

void display(treeNode* nd)
{
    if(nd != NULL)
        printf("%d ",nd->item);
}
void display_tree(treeNode* nd)
{
    if (nd == NULL)
        return;
    /* display node item */
    printf("%d",nd->item);
    if(nd->left != NULL)
        printf("(L:%d)",nd->left->item);
    if(nd->mid != NULL)
        printf("(R:%d)",nd->mid->item);
    if(nd->right != NULL)
        printf("(R:%d)",nd->right->item);
    printf("\n");

    display_tree(nd->left);
    display_tree(nd->mid);
    display_tree(nd->right);
}


int main(void)
{
    treeNode* root = NULL;
    comparer int_comp = compare;



    int a[SIZE] = {8,3,10,1,6,14,4,7,13,15,2,5,20};
    int i;
    printf("--- C Binary Search Tree ---- \n\n");
    printf("Insert: ");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ",a[i]);
        root = insert_node(root,int_comp,a[i]);
    }
    printf(" into the tree.\n\n");

    /* display the tree */
    display_tree(root);

    /* remove element */
int r;
    do
    {
        printf("Enter data to remove, (-1 to exit):");
        scanf("%d",&r);
        if(r == -1)
            break;
        root = delete_node(root,r,int_comp);
        /* display the tree */
        if(root != NULL)
            display_tree(root);
        else
            break;
    }
    while(root != NULL);
    /* search for a node */

    int key = 0;
    treeNode* s;
    while(key != -1)
    {
        printf("Enter item to search (-1 to exit):");
        scanf("%d",&key);

        s = search(root,key,int_comp);
        if(s != NULL)
        {
            printf("Found it %d",s->item);
            if(s->left != NULL)
                printf("(L: %d)",s->left->item);
            if(s->mid != NULL)
                printf("(R: %d)",s->mid->item);
            if(s->right != NULL)
                printf("(R: %d)",s->right->item);
            printf("\n");
        }
        else
        {
            printf("node %d not found\n",key);
        }
    }

    /* remove the whole tree */
    dispose(root);
    return 0;
}
}

**Nepomuk** · May 30 '13, 02:31 PM

OK... Well, first of all: In what way doesn't it work? Have you tested parts of it? Just writing code without testing it ever so often is not a good idea, as it's more difficult to find errors that way.

Here are errors I can find without testing or fixing the code myself:

I'm not aware of a malloc.h header file; this may depend on the compiler though.
In line 23 you seem to want to compare a and b with the line b<a<=b+5. This will not however find out, whether b<a and a<=b+5. What it will do is this assuming a = b + 6 and b > -5:
Code:
```
b < a <= b + 5
(b < a) <= b + 5
1 <= b + 5
1
```
This is because there's no own boolean primitive data type in C and instead false = 0 and true = every other number. What you want instead is this:
Code:
```
if(b < a && a <= b + 5) ...
```
In line 82 you return root within the method insertNode(...). This is not correct, as a void method will not return an element. As you use the result of that call later, I asume it should have a different type?
In line 84 you start a new function (search) while you're still in the insertNode method. Same with delete_node in line 104, dispose in line 138 and so on.
You define comparer twice: In line 17 and line 44.
In line 5 you define SIZE as 9. In 181 you create an array with SIZE elements but then hand it 13.
In line 188 you call a method called insert_node while in line 45 you define a method called insertNode. I guess, those should be the same?

That should be enough to get it to compile; then we can get it to do what it should.

how to implement general (each node) tree with c program

how to implement general (each node) tree with c program

Comment

Comment

Comment