binary search tree problems

extincty's Avatar, Join Date: Apr 2008
Newbie Member
Code:


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

#define MAX 100

typedef struct node{
	struct node *left;
	int data;
	struct node *rt;
}BST;

void insert(BST **b,int num);
void inorder(BST *);
void preorder(BST *);
void postorder(BST *);

int count(BST *s);
int search(BST **s,int fnd);
void dlt(BST **s,int);

BST *b;
int ch,ch1,num,cnt=0,fnd,srch,nmbr;

void main()
{    
	while(1){
		clrscr();
		printf("\n1.insert\n2.search\n3.traversal\n4.delete\n5.count\n6.exit");
		printf("\nenter your choice: ");
		printf("\n(no 4 is inactive.dont press it): ");
		scanf("\t%d",&ch);
		switch(ch){
			case 1:  printf("enter a data: ");
						scanf("%d",&num);
						fnd=search(&b,num);
						if(fnd==0)	insert(&b,num);
						else{
							printf("\nelement already present in the list\n");
							getch();
						}
						break;
			case 2:  printf("enter the number you want to search in the list: ");
						scanf("%d",&srch);
						fnd=search(&b,srch);
						if(fnd==0)	printf("\nnot found\n");
						else	printf("\nelement found\n");
						getch();
						break;
			case 3:	printf("which traversal technique you want to follow:\n");
						printf("1.inorder\n2.preorder\n3.postorder");
						printf("\nyour choice is: ");
						scanf("%d",&ch1);
						switch(ch1){
							case 1:	inorder(b);
										getch();
										break;
							case 2:	preorder(b);
										getch();
										break;
							case 3:	postorder(b);
										getch();
										break;
						}	// end of inner switch-case
						break;
			case 4:  printf("enter th enumber you want to delete: ");
						scanf("%d",&nmbr);
						fnd=search(&b,nmbr);
						if(fnd==0)	printf("\nnot found\n");
						else	dlt(&b,nmbr);
						getch();
						break;
			case 5:	cnt=count(b);
						if(cnt==0)	printf("\nlist is empty\n");
						else	printf("\nthere are %d elements present in the list",cnt);
						getch();
						break;
			case 6:	exit(0);
						break;
			default:	printf("you are entering a wrong choice\n\n");
         			getch();
		}	// end of outer switch-case
	}	// end of while
}	// end of main


void insert(BST **s,int num)
{
	if(*s==NULL){
		*s=(BST*)malloc(sizeof(BST));
		(*s)->left=NULL;
		(*s)->data=num;
		(*s)->rt=NULL;
		return;
	}
	if(num<(*s)->data)	insert((&(*s)->left),num);
	else	insert((&(*s)->rt),num);
	return;
}

void inorder(BST *s)
{
	if(s!=NULL){
		inorder(s->left);
		printf("\t%d",s->data);
		inorder(s->rt);
	}
	else	return;
}

void preorder(BST *s)
{
	if(s!=NULL){
		printf("\t%d",s->data);
		preorder(s->left);
		preorder(s->rt);
	}
	else	return;
}

void postorder(BST *s)
{
	if(s!=NULL){
		postorder(s->left);
		postorder(s->rt);
		printf("\t%d",s->data);
	}
	else	return;
}

int search(BST **s,int num)
{
	if(*s==NULL)	return 0;
	else if(num > (*s)->data)	search((&(*s)->rt),num);
	else if(num < (*s)->data)	search((&(*s)->left),num);
	else if(num == (*s)->data)	return 1;
}

int count(BST *s)
{
	int a[MAX],i=0,c=0;
	if(s!=NULL){
		count(s->left);
		count(s->rt);
      a[i]=s->data;
		i++;
	}
/*		a[i]='\0';
		while(a[i]!='\0'){
			c++;
			i++;
		}
		return c;*/
		return i;
}


void dlt(BST **s,int nmbr)
{
	int c;
	printf("delete operation\n\n");
}
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Please do not attach the code into text file. I have removed the text file and updated the post to have the code.