Posts Tagged Binary tree
program to generate a binary tree in C.
Posted by admin in C Examples on July 1st, 2009
#include<stdio.h>
int x;
struct nodetype
{
int info;
struct nodetype *left,*right;
};
typedef struct nodetype *nodeptr;
nodeptr root;
nodeptr maketree(int x);
void setleft(nodeptr p,int x);
void setright(nodeptr p,int x);
void search(int x,nodeptr p);
void inorder(nodeptr p);
main()
{
FILE *fp=fopen("binaryfile.c","r");
fscanf(fp,"%d",&x);
root=maketree(x);
while((fscanf(fp,"%d",&x))!=EOF)
search(x,root);
inorder(root);
}
void search(int x,nodeptr p)
{
if(x==(p->info)){
printf("duplicate found");
}
else if(x<(p->info))
if((p->left)==NULL)
setleft(p,x);
else search(x,p->left);
else if((p->right)==NULL)
setright(p,x);
else search(x,p->right);
}
nodeptr maketree(int x)
{
nodeptr p;
p=(struct nodetype *)malloc(sizeof(struct nodetype));
(p->info)=x;
(p->left)=NULL;
(p->right)=NULL;
return p;
}
void setleft(nodeptr p,int x)
{
if(p==NULL)
printf("error");
else if((p->left)!=NULL)
printf("/nerror");
else (p->left)=maketree(x);
}
void setright(nodeptr p,int x)
{
if(p==NULL)
printf("error");
else if((p->right)!=NULL)
printf("/nerror");
else (p->right)=maketree(x);
}
void inorder(nodeptr p)
{
if(p==NULL)
return;
else{
inorder(p->left);
printf("\n%d",p->info);
inorder(p->right);
}
return;
}
Deleting a node in a binary tree
Posted by admin in C Examples on June 24th, 2009
In addition to techniques for inserting data in a binary tree and traversing the tree, practical examples call for deleting data from the binary tree. Assuming that we will pass the specified data item that we wish to delete to the delete( ) function, there are four possible cases that we need to consider:
- No node in the tree contains the specified data.
- The node containing the data has no children.
- The node containing the data has exactly one child.
- The node containing the data has two children.
/* Program to to delete a node form a binary search tree */
#include "alloc.h"
#define TRUE 1
#define FALSE 0
struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;
main( )
{
struct btreenode *bt ;
int req, i = 0, num, a[ ]= { 11, 9, 13, 8, 10, 12, 14, 15, 7 } ;
bt = NULL ;/* empty tree */
clrscr( ) ;
while ( i <= 8 )
{
insert ( &bt, a[i] ) ;
i++ ;
}
clrscr( ) ;
printf ( "Binary tree before deletion: " ) ;
inorder ( bt ) ;
delete ( &bt, 10 ) ;
printf ( "\nBinary tree after deletion: " ) ;
inorder ( bt ) ;
delete ( &bt, 14 ) ;
printf ( "\nBinary tree after deletion: " ) ;
inorder ( bt ) ;
delete ( &bt, 8 ) ;
printf ( "\nBinary tree after deletion: " ) ;
inorder ( bt ) ;
delete ( &bt, 13 ) ;
printf ( "\nBinary tree after deletion: " ) ;
inorder ( bt ) ;
}
/* inserts a new node in a binary search tree */
insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;
( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num ;
( *sr ) -> rightchild = NULL ;
return ;
}
else /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
/* else traverse to right */
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
return ;
}
/* deletes a node from the binary search tree */
delete ( struct btreenode **root, int num )
{
int found ;
struct btreenode *parent, *x, *xsucc ;
/* if tree is empty */
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}
parent = x = NULL ;
/* call to search function to find the node to be deleted */
search ( root, num, &parent, &x, &found ) ;
/* if the node to deleted is not found */
if ( found == FALSE )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}
/* if the node to be deleted has two children */
if ( x -> leftchild != NULL && x -> rightchild != NULL)
{
parent = x ;
xsucc = x -> rightchild ;
while ( xsucc -> leftchild != NULL )
{
parent = xsucc ;
xsucc = xsucc -> leftchild ;
}
x -> data = xsucc -> data ;
x = xsucc ;
}
/* if the node to be deleted has no child */
if ( x -> leftchild == NULL && x -> rightchild == NULL )
{
if ( parent -> rightchild == x )
parent -> rightchild = NULL ;
else
parent -> leftchild = NULL ;
free ( x ) ;
return ;
}
/* if the node to be deleted has only rightchild */
if ( x -> leftchild == NULL && x -> rightchild != NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> rightchild ;
else
parent -> rightchild = x -> rightchild ;
free ( x ) ;
return ;
}
/* if the node to be deleted has only left child */
if ( x -> leftchild != NULL && x -> rightchild == NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> leftchild ;
else
parent -> rightchild = x -> leftchild ;
free ( x ) ;
return ;
}
}
/* returns the address of the node to be deleted, address of its parent and whether the node is found or not */
search ( struct btreenode **root, int num, struct btreenode **par, struct btreenode **x, int *found )
{
struct btreenode *q ;
q = *root ;
*found = FALSE ;
*par = NULL ;
while ( q != NULL )
{
/* if the node to be deleted is found */
if ( q -> data == num )
{
*found = TRUE ;
*x = q ;
return ;
}
if ( q -> data > num )
{
*par = q ;
q = q -> leftchild ;
}
else
{
*par = q ;
q = q -> rightchild ;
}
}
}
/* traverse a binary search tree in a LDR (Left-Data-Right) fashion */
inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;
/* print the data of the node whose leftchild is NULL or the path has already been traversed */
printf ( "%d ", sr -> data ) ;
inorder ( sr -> rightchild ) ;
}
else
return ;
}
Program to implement binary tree and print value of nodes in ascending order
Posted by admin in C Examples on June 24th, 2009
Such a binary tree that has the property that all elements in the left subtree of a node n are less than the contents of n, and all elements in the right subtree of n are greater than or equal to the contents of n. A binary tree that has this property is called a Binary Search tree. If a binary search tree is traversed in inorder (left, root, right) and the contents of each node are printed as the node is visited, the numbers are printed in ascending order. Convince yourself that this is the case for the binary search tree. The program to implement this algorithm is given below:
/* Program to implement a binary tree */
#include"alloc.h"
struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;
main( )
{
struct btreenode *bt ;
int req, i = 1, num ;
bt = NULL ; /* empty tree */
clrscr( ) ;
printf ( "Specify the number of data items to be inserted: " ) ;
scanf ( "%d", &req ) ;
while ( i++ <= req )
{
printf ( "Enter the data :" ) ;
scanf ( "%d", &num ) ;
insert (&bt, num ) ;
}
clrscr( ) ;
printf ( "\nInorder Traversal:" ) ;
inorder ( bt ) ;
printf ( "\nPreorder Traversal:" ) ;
preorder ( bt ) ;
printf ( "\nPostorder Traversal: " ) ;
postorder ( bt ) ;
}
/* inserts a new node in a binary search tree */
insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;
( *sr ) -> leftchild = NULL ;
( *sr ) -> data =num ;
( *sr ) -> rightchild = NULL ;
return ;
}
else /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
/* else traverse to right */
insert (&( ( *sr ) -> rightchild ), num ) ;
}
return ;
}
/*traverse a binary search tree in a LDR (Left-Data-Right) fashion */
inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ; /* print the data of the node whose leftchild is NULL or the path
has already been traversed */
printf ( "%d ", sr-> data ) ;
inorder ( sr -> rightchild ) ;
}
else
return ;
}
/* traverse a binary search tree in a DLR (Data-Left-right) fashion */
preorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
/* print the data of a node */
printf ( "%d ", sr -> data ) ; /* traverse till leftchild is not NULL */
preorder ( sr -> leftchild ) ;
/* traverse till rightchild is not NULL */
preorder ( sr -> rightchild ) ;
}
else
return ;
}
/* traverse a binary search tree in LRD (Left-Right-Data) fashion */
postorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
postorder ( sr -> leftchild ) ;
postorder ( sr -> rightchild ) ;
printf ( "%d ", sr -> data ) ;
}
else
return ;
}
PROGRAM TO GENERATE BINARY TREE AND FIND ITS DEPTH.
Posted by admin in C++ Examples on June 6th, 2009
#include<iostream.h>#include<fstream.h>
#include<ctype.h>
#include<conio.h>
int dup=0;
struct bintree
{
int data;
bintree *left,*right;
};
struct avltree
{
int data,diff;
bintree *left,*right;
};
fstream file;
void makenode(bintree **garb,int num)
{
(*garb)->data=num;
(*garb)->left=NULL;
(*garb)->right=NULL;
}
void makebintree(bintree *garb,bintree **base)
{
if((*base)==NULL)
{
*base=garb;
return;
}
else if(garb->data==(*base)->data)
{
cout<<" "<<garb->data;
dup++;
return;
}
else if(garb->data<(*base)->data)
makebintree(garb,&((*base)->left));
else
makebintree(garb,&((*base)->right));
}
int depth(bintree *node)
{
int l,r;
if(node==NULL)
return -1;
l=1+depth(node->left);
r=1+depth(node->right);
return ((l>r)?l:r);
}
void dump(bintree **node)
{
if(*node==NULL)
return;
if((*node)->left==NULL&&(*node)->right==NULL)
{
delete(*node);
*node=NULL;
}
else
{
dump(&((*node)->left));
dump(&((*node)->right));
dump(node);
}
}
void main()
{
bintree *garb,*root=NULL;
int num;
file.open("datab2.txt",ios::in);
cout<<"\n DUPLICATE ELEMENTS ARE : \n";
while(file>>num)
{
garb=new bintree;
makenode(&garb,num);
makebintree(garb,&root);
}
cout<<"\n DEPTH="<<depth(root);
cout<<"\n NO.of dup="<<dup;
dump(&root);
file.close();
}
PROGRAM TO GENERATE A FILE WITH 10000 DISTINCT RANDOM NUMBERS PROGRAM USES BINARY TREE.
Posted by admin in C++ Examples on June 6th, 2009
#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
int total=0;
fstream file;
struct bintree
{
int data;
bintree *left,*right;
};
void makenode(bintree **garb,int num)
{
(*garb)->data=num;
(*garb)->left=NULL;
(*garb)->right=NULL;
}
void makebintree(bintree *garb,bintree **base)
{
if((*base)==NULL)
{
*base=garb;
total++;
file<<garb->data<<" ";
return;
}
else if(garb->data==(*base)->data)
{
return;
}
else if(garb->data<(*base)->data)
makebintree(garb,&((*base)->left));
else
makebintree(garb,&((*base)->right));
}
void dump(bintree **node)
{
if(*node==NULL)
return;
if((*node)->left==NULL&&(*node)->right==NULL)
{
delete(*node);
*node=NULL;
}
else
{
dump(&((*node)->left));
dump(&((*node)->right));
dump(node);
}
}
void main()
{
bintree *garb,*root=NULL;
file.open("datab2.txt",ios::out);
while(total<10000)
{
garb=new bintree;
makenode(&garb,rand());
makebintree(garb,&root);
}
dump(&root);
file.close();
}
-
FeedCount
Recent Comments