Search Tutorials

Saturday, 20 April 2013

C code to implement Binary Search Tree using Father Field

/* C program to implement binary search tree using father field */

#include <stdio.h>

/* Parent field=father field*/
struct st
{
    int data;
    struct st* lc;
    struct st* rc;
    struct st* parent;
};

struct st *root=NULL;
struct st * find_leftmost(struct st *);
struct st * find_succ(struct st *, struct st *);
struct st * insert(struct st *,int);

int main()
{
  struct st* temp, *succ;
  int ch,ele,n,i;
  clrscr();
  while(1)
    {
    printf("\n\t\tMENU\n\t1.To insert\n\t2.For inorder Traversal\n\t0.To exit\n\t");
    scanf("%d",&ch);

        switch(ch)
        {
         case 1:
            printf("\n\tEnter number of elements\n\t");
            scanf("%d",&n);
            printf("\n\tEnter %d numbers to be inserted \n\t: ",n);
            for(i=0;i<n;i++)
            {
            printf("\n\t");
            scanf("%d",&ele);
            root=insert(root,ele);
            }
           break;
         case 2:
         clrscr();
         printf("\n\tInorder traversal using Father field\n\t");
         temp=find_leftmost(root);
         printf("%d ",temp->data);
         a:
         succ=find_succ(root,temp);
         if(succ !=  NULL)
         {
            printf("%d ",succ->data);
            temp=succ;goto a;
         }
        break;
        case 0:
        getch();
        exit(0);
        default:printf("Wrong choice pleas enter valid option  ");
        }
    }
}

/* Creating binary search tree using parent field */

struct st* insert(struct st* root, int ele)
{
    struct st *temp;
    if (root== NULL)
    {
    struct st* root = (struct st*)
    malloc(sizeof(struct st));
    root->data   = ele;
    root->lc   = NULL;
    root->rc  = NULL;
    root->parent = NULL;
    return(root);
    }
  else
  {
    if (ele <= root->data)
    {
     temp = insert(root->lc, ele);
     root->lc  = temp;
     temp->parent= root;
    }
    else
    {
    temp = insert(root->rc, ele);
    root->rc = temp;
    temp->parent = root;
    }
       return root;
  }
}

/* Finding left most node */

struct st * find_leftmost(struct st* node) {
    struct st* current = node;
    while (current->lc != NULL) {
    current = current->lc;
  }
  return current;
}

/* Finding succeeder of the node  */

struct st * find_succ(struct st *root, struct st *n)
{
   struct st *p;
    if( n->rc != NULL )
    return find_leftmost(n->rc);
    p= n->parent;
   while(p != NULL && n == p->rc)
   {
     n = p;
     p = p->parent;
   }
  return p;
}

/* Output of Binary Search Tree using Father Field Program */

C code to implement Binary Search Tree using father field
Output of BST using Father Field

C code to implement Binary Search Tree using father field
Output of BST using Father Field

For more related to Data Structure check List of Data Structure Programs. If you like this program, Please share and comment to improve this blog.

5 comments:

  1. Hey There. I found your post using msn. This is a really well written article. I will make sure to bookmark it and come back to read more of your useful information. Thanks for the post. I will certainly comeback. best seo company singapore

    ReplyDelete
  2. I really like your blog.. very nice colors & theme. Did you make this website yourself or did you hire someone to do it for you? Plz answer back as I'm looking to design my own blog and would like to know where u got this from. appreciate itsocial advertisement

    ReplyDelete
  3. I’m not that much of a internet reader to be honest but your sites really nice, keep it up! I'll go ahead and bookmark your website to come back down the road. All the best Parc clematis psf

    ReplyDelete
  4. excellent points altogether, you just gained a new reader. What would you suggest in regards to your post that you made a few days ago? Any positive? concrete cylinder

    ReplyDelete
  5. Hey! Quick question that's totally off topic. Do you know how to make your site mobile friendly? My blog looks weird when browsing from my iphone 4. I'm trying to find a template or plugin that might be able to correct this issue. If you have any recommendations, please share. Many thanks! dental crown cost singapore

    ReplyDelete

Back to Top