#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
#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