Print Level Order binary tree Linked List implementation (BST)

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


/*Binary tree node implementation for Linked List*/
struct node
{
      
       struct node *llink;
       int info;
       struct node *rlink;
      
};
typedef struct node SNODE;

/*Queue node implementation for Linked List*/
struct qnode
{
SNODE *info;
struct qnode *link;
};
typedef struct qnode QNODE;



/* Functions for Creating Binary tree and displaying it in tree format */
void insert(SNODE **,int);
void display(SNODE **,int);
void bst(SNODE **,SNODE **);

/* Function to print the nodes of a binary tree in a level-wise manner format */
void printLevelOrder(SNODE **);
SNODE* dequeue(QNODE **);
void enqueue(QNODE **,QNODE **,SNODE **);


/* Function for inserting a node in binary search tree */
void insert(SNODE **proot,int val)
{
     SNODE *pnew,*pcurr;
    
     /* Setting Current node to the Root node of the binary tree */
     pcurr=*proot;
    
     /* Initialing new node of the binary tree */
     pnew=(SNODE*)malloc(sizeof(SNODE));
     pnew->llink=NULL;
     pnew->info=val;
     pnew->rlink=NULL;
    
      /* Initializing the binary tree root node if null*/
     if(*proot==NULL)
     {
          *proot=pnew;
     }
      /* if not null then search and place the node on the right position of the binary search tree*/
     else
     {
                  
                   bst(&pcurr,&pnew);
     }
}
/* Function for displaying binary tree nodes in tree format */
void display(SNODE **proot,int level)
{
     SNODE *pcurr;
     int i;
    
     pcurr=*proot;
     if(pcurr!=NULL)
     {
                    /* Print all the nodes of right tree from the root node */
                    display(&(pcurr->rlink),level+1);
                  
                    /* Print tab space according to the level */
                    for(i=1;i<level;i++)
                            printf("\t");
                                      
                    printf("%d\n\n",pcurr->info);
                    /* Print all the nodes of left tree from the root node */
                    display(&(pcurr->llink),level+1);
                  
     }
}
/* Function for searching and placing the node of binary tree nodes in a right position */
void bst(SNODE **proot,SNODE **pne)
{
        SNODE *pcurr,*pnew;
        pcurr=*proot;
        pnew=*pne;
      
        /*if node value not in binary search tree then find and place the node on right pos */
        if((pcurr->info)!=(pnew->info))
        {
                                       /* if new node value is less then the current node's value and its left link is not empty */
                                       if((pcurr->info > pnew->info)&&(pcurr->llink!=NULL))
                                       {
                                                       bst(&(pcurr->llink),&pnew);
                                       }
                                       /* if new node value is greater then the current node's value and its right link is not empty */
                                       else
                                       if((pcurr->info < pnew->info)&&(pcurr->rlink!=NULL))
                                       {
                                                       bst(&(pcurr->rlink),&pnew);
                                       }
                                       else
                                       /* if found a empty position then place it the new node according to the cond. in the binary tree */
                                           (pcurr->info > pnew->info) ? (pcurr->llink=pnew): (pcurr->rlink=pnew);
        }
}
/* Function for displaying binary tree nodes in Level wise mannner*/
void printLevelOrder(SNODE **proot)
{
    
     SNODE *pcurr;
     QNODE *pfront,*prear;
    
      /* initializing current ,front and rear node*/
     pcurr=*proot;
     pfront=NULL;
     prear=NULL;

     while(pcurr)
     {

                 printf("%d ", pcurr->info);

                 /*Enqueue left child */
  
                 if(pcurr->llink)
                 enqueue(&pfront, &prear, &(pcurr->llink));

                 /*Enqueue right child */
  
                 if(pcurr->rlink)
                 enqueue(&pfront, &prear, &(pcurr->rlink));

                 /*Dequeue node and make it pcurr or current node*/
                 if(pfront==NULL)
                 break;
                 pcurr = dequeue(&pfront);

     }

/* Function for Enqueueing a node in the queue*/
void enqueue(QNODE **apfront,QNODE **aprear,SNODE **pnew)
{
    
        QNODE *qnew;
         /* initialize the queue node*/
qnew=(QNODE *)malloc(sizeof(QNODE));
qnew->info=*pnew;
qnew->link=NULL;

    /* Initialize the queue if its is null*/
if(*apfront==NULL)
{
*apfront=qnew;
*aprear=qnew;
}
 /*if queue not null then enqueue the node at the rear of the queue*/
else
{
             /* creating linkto the new node */
    (*aprear)->link=qnew;
   
     /* setting queue rear at the new node*/
    *aprear=qnew;
}


}
/* Function for dequeueing a node from the queue*/
SNODE* dequeue(QNODE **pfront)
{
QNODE *pdel;
SNODE *pnode;

pdel=*pfront;

     /*saving the info of the dequeued node */
pnode=pdel->info;

     /* deleting link of the node to dequeue it*/
(*pfront)=(*pfront)->link;

    /* Free memory for the dequeued node */
free(pdel);

 /* Returning the dequeued node to the caller func*/
return pnode;

}


int main()
{
    SNODE *proot;
    proot=NULL;
  
     /* insertion of nodes in abinary tree*/
    insert(&proot,10);
    insert(&proot,7);
    insert(&proot,20);
    insert(&proot,1);
    insert(&proot,78);
    insert(&proot,9);
    insert(&proot,16);
    insert(&proot,4);
    insert(&proot,14);
  
     /* displaying nodes in a tree format horizontally which starts 10 as root node*/
    display(&proot,2);
  
     /* displaying nodesin a level wise mannner */
    printLevelOrder(&proot);
  
    getch();
}


THANK YOU FOR VISITING..!!
PLEASE COMMENT

No comments:

Post a Comment