Posts Tagged binary search tree
Program for binary search tree in C++.
Posted by admin in C++ Examples on July 2nd, 2009
#include<iostream.h> //INCLUDING LIBRARIES
#include<fstream.h>
struct node //DECLARING NODE DATA STRUCTURE
{
int data;
node *left, *right;
}*root, *cur ,*temp;
void pretrav (node *); //FUNCTION PROTOTYPE FOR PRETRAVERSAL OF BINARY TREE
void intrav (node *); //FUNCTION PROTOTYPE FOR INORDER TRAVERSAL OF BINARY TREE
void posttrav (node *); //FUNCTION PROTOTYPE FOR POSTTRAVERSAL OF BINARY TREE
void main() //START OF MAIN
{
cout<<"\t\t\t BINARY SEARCH TREE\n\n";
cout<<"\n\nDuplicates in the tree : ";
char ch,sign;
int num,count=0,countdup=0;;
ifstream fin;
fin.open("integer.txt"); //OPENING TEXT FILE CONTAINING INTEGERS AND STORING THE RETURNED PTR IN FIN
while(fin) //EXECUTE THE LOOP TILL THE END OF FILE
{
fin.get(ch); //READ A CHARACTER FROM THE FILE
if (ch==' ') //IF SPACE CONTINUE
continue;
if (ch=='+'||ch=='-') //STORING THE SIGN OF NUMBER
sign=ch;
if (ch>='0'&&ch<='9') //IF DIGIT ENCOUNTERED
{
fin.seekg(-1,ios::cur);
fin>>num; //READING NUMBER IF DIGIT ENCOUNTERED
count++; //INCREMENTING THE COUNTER
if (sign=='-') //MAKING THE NUMBER NEGATIVE AND STORING IN NUM
num=0-num;
sign='+'; //MAKING SIGH POSITIVE ...DEFAULT
temp=new node; //CREATING NEW NODE
temp->data=num; //STORING THE NUM IN NEW NODE
temp->left=temp->right=NULL; //MAKING LEFT & RIGHT PTRS OF TEMP NULL
cur=root; //POINTING CUR PTR TO THE ROOT
if (count==1) //IF ITS FIRST NODE MAKE IT ROOT
root=temp;
else
{
while(1)
{
if (cur->data<temp->data)
{
if (cur->right!=NULL)
cur=cur->right; //MOVING CUR POINTER
else
{
cur->right=temp;
break; //EXIT OUT OF WHILE LOOP
}
}
if (cur->data>temp->data)
{
if (cur->left!=NULL)
cur=cur->left; //MOVING CUR POINTER
else
{
cur->left=temp;
break; //EXIT OUT OF WHILE LOOP
}
}
if (cur->data==temp->data)
{
cout<<num<<" "; //PRINTING DUPLICATES
countdup++;
break;
}
}
}
}
}
if (countdup==0)
cout<<" None";
cout<<"\n\nPreorder Traversal of the Tree : ";
pretrav(root); //CALLING FUNCTION FOR PREORDER TRAVERSAL OF TREE PASSING ROOT
cout<<endl<<endl;
cout<<"Inorder Traversal of the Tree : ";
intrav (root); //CALLING FUNCTION FOR INORDER TRAVERSAL OF TREE PASSING ROOT
cout<<endl<<endl;
cout<<"Postorder Traversal of the Tree: ";
posttrav(root); //CALLING FUNCTION FOR POSTORDER TRAVERSAL OF TREE PASSING ROOT
cout<<endl<<endl;
}
void pretrav (node * point) //DECLARING FUNCTION FOR PRETRAVERSAL OF THE TREE
{
cout<<" "<<point->data<<" ";
if (point->left!=NULL)
pretrav (point->left);
if (point->right!=NULL)
pretrav (point->right);
}
void intrav (node * point) //DECLARING FUNCTION FOR INORDER TRAVERSAL OF THE TREE
{
if (point->left!=NULL)
intrav (point->left);
cout<<" " <<point->data<<" ";
if (point->right!=NULL)
intrav (point->right);
}
void posttrav (node *point) //DECLARING FUNCTION FOR POSTORDER TRAVERSAL OF THE TREE
{
if (point->left!=NULL)
intrav (point->left);
if (point->right!=NULL)
intrav (point->right);
cout<<" " <<point->data<<" ";
}
//END OF PROGRAM//
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;
}
PROGRAM TO MAKE A BINARY SEARCH TREE AND TRAVERSE IT IN PREORDER,INORDER,POSTORDER METHOD.
Posted by admin in C++ Examples on May 17th, 2009
#include<iostream.h> //HEADER FILES
#include<ctype.h>
#include<stdio.h>
struct tree //STRUCTURE FOR TREE NODE
{
int data;
tree *left,*right;
}; //STRUCTURE FOR LIST
struct list
{
int num;
list * next;
};
list *head=NULL,*temp,*curr;
FILE* file;
void put(int no) //PUT NO. INTO LIST
{
temp=new list;
temp->num=no;
temp->next=NULL;
if(head==NULL)
{
head=temp;
curr=temp;
}
else
{
curr->next=temp;
curr=temp;
}
}
void getdata()
{
char ch;
int no,flag=1;
file=fopen("input.txt","r");
do
{
if(flag)
{
no=0;
flag=0;
}
ch=getc(file);
if(isdigit(ch))
no=no*10+ch-48;
else if(ch==' ')
{
flag=1;
put(no);
}
}while(ch!='n');
fclose(file);
}
void makenode(tree **garb,int num) //PREPARE A NODE
{
(*garb)->data=num;
(*garb)->left=NULL;
(*garb)->right=NULL;
}
void maketree(tree *garb,tree **base) //INSERT NODE INTO TREE
{
if((*base)==NULL)
{
*base=garb;
return;
}
else if(garb->data==(*base)->data)
{
cout<<" "<<garb->data;
return;
}
else if(garb->data<(*base)->data)
maketree(garb,&((*base)->left));
else
maketree(garb,&((*base)->right));
}
void preorder(tree *node) //PREORDER TRAVERSAL
{
cout<<" "<<node->data;
if(node->left!=NULL)
preorder(node->left);
if(node->right!=NULL)
preorder(node->right);
}
void inorder(tree *node) //INORDER TRAVERSAL
{
if(node->left!=NULL)
inorder(node->left);
cout<<" "<<node->data;
if(node->right!=NULL)
inorder(node->right);
}
void postorder(tree *node) //POST ORDER TRAVERSAL
{
if(node->left!=NULL)
postorder(node->left);
if(node->right!=NULL)
postorder(node->right);
cout<<" "<<node->data;
}
void main() //EXECUTION STARTS HERE
{
tree *garb,*root=NULL;
getdata();
temp=head;
cout<<"n DUPLICATE ELEMENTS ARE : n";
while(temp!=NULL)
{
garb=new tree;
makenode(&garb,temp->num);
maketree(garb,&root);
temp=temp->next;
}
cout<<"n PREORDER TRAVERSE :";
preorder(root);
cout<<"n INORDER TRAVERSE :";
inorder(root);
cout<<"n POSTORDER TRAVERSE :";
postorder(root);
free(garb);
free(root);
cout<<"n";
}
-
FeedCount
Recent Comments