Monday, January 2, 2012

Binary Search Tree - C

I got a bit bored today, and wrote this to pass some time. Nothing's special here, but a normal binary search tree implementation in C. I just felt that some other stuff found online to be a little complicated for beginners, well, here is the simplest I could manage.



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

//Create a node, well in layman's terms, a layout for a container, ie. the container should have one compartment to store the actual data, and two compartments to store the addresses of the children

struct node
{
    struct node *left,*right;
    int item;
};

//To insert something we need the data, passing the head could have been avoided had I kept it as a global variable

void insert(int item,struct node *head)
{
    struct node *tmpNode;
    tmpNode =  (struct node *)malloc(sizeof(struct node));
    tmpNode->item = item;
    tmpNode->right = tmpNode->left = NULL;
    findplaceNinsert(tmpNode,head);
    return;
}
//Keep traversing by going either left or right depending on the values, and insert as soon as we find an empty slot

void findplaceNinsert(struct node *tmpNode, struct node *parent)
{
    if(tmpNode->item > parent->item)
    {//Go right
        if(parent->right == NULL) parent->right = tmpNode;
        else findplaceNinsert(tmpNode,parent->right);
    }
    else
    {//Go left
        if(parent->left == NULL) parent->left = tmpNode;
        else findplaceNinsert(tmpNode,parent->left);
    }
    return;
}
//Inorder traversal
void printInorder(struct node *tmpNode)
{
    if(tmpNode->left != NULL) printInorder(tmpNode->left);
    printf("%d ",tmpNode->item);
    if(tmpNode->right != NULL) printInorder(tmpNode->right);
}

int main()
{
    struct node *head;
    int i,item;

    srand(time(NULL));
   
    head = (struct node *)malloc(sizeof(struct node));
    head->left = head->right = NULL;
    head->item = rand()%100;

    printf("\nInserting random numbers...\n");
    for(i=0;i<15;i++)
    {
        item = rand()%100;
        insert(item,head);
        printf("%d ",item);
    }
   
    printf("\n");
    printInorder(head);
}

1 comment:

  1. Jesso'S Blog: Binary Search Tree - C >>>>> Download Now

    >>>>> Download Full

    Jesso'S Blog: Binary Search Tree - C >>>>> Download LINK

    >>>>> Download Now

    Jesso'S Blog: Binary Search Tree - C >>>>> Download Full

    >>>>> Download LINK

    ReplyDelete