من اینو دارم نمی دونم همینیه که می خوای یا نه ؟
#include <iostream.h>
#include <process.h>
#include <conio.h>
#include <graphics.h>
#include <stdio.h>
#include <stdlib.h>
#include <process.h>
struct node{
struct node *left;
int data;
struct node *right;
};
class BST{
public:
node * tree;
void createTree(node **,int item);
void preOrder(node *);
void inOrder(node *);
void postOrder(node *);
void determineHeight(node *,int *);
int totalNodes(node *);
int internalNodes(node *);
int externalNodes(node *);
void removeTree(node **);
node **searchElement(node **,int);
int findSmallestNode(node *);
int findLargestNode(node *);
void deleteNode(int);
BST(){
tree=NULL;
}
};
void BST :: createTree(node **tree,int item)
{
if(*tree == NULL)
{ *tree = new node;
(*tree)->data = item;
(*tree)->left = NULL;
(*tree)->right = NULL;
}
else
{
if( (*tree)->data > item)
createTree( &((*tree)->left),item);
else //
createTree( &((*tree)->right),item);
}
}
void BST :: preOrder(node *tree){
if( tree!=NULL){
cout<<" "<< tree->data;
preOrder(tree->left);
preOrder(tree->right);
}
}
void BST :: inOrder(node *tree){
if( tree!=NULL){
inOrder( tree->left);
cout<<" "<< tree->data;
inOrder(tree->right);
}
}
void BST :: postOrder(node *tree){
if( tree!=NULL){
postOrder( tree->left);
postOrder( tree->right);
cout<<" "<<tree->data;
}
}
void BST :: determineHeight(node *tree, int *height){
int left_height, right_height;
if( tree == NULL)
*height = 0;
else{
determineHeight(tree->left, &left_height);
determineHeight(tree->right, &right_height);
if( left_height > right_height)
*height = left_height + 1;
else
*height = right_height + 1;
}
}
int BST :: totalNodes(node *tree){
if( tree == NULL)
return 0;
else
return( totalNodes(tree->left) + totalNodes(tree->right) + 1 );
}
int BST :: internalNodes(node *tree){
if( (tree==NULL) || (tree->left==NULL && tree->right==NULL))
return 0;
else
return( internalNodes(tree->left) + internalNodes(tree->right) + 1 );
}
int BST :: externalNodes(node *tree){
if( tree==NULL )
return 0;
else if( tree->left==NULL && tree->right==NULL)
return 1;
else
return( externalNodes(tree->left) + externalNodes(tree->right));
}
node ** BST :: searchElement(node **tree, int item){
if( ((*tree)->data == item) || ( (*tree) == NULL) )
return tree;
else if( item < (*tree)->data)
return searchElement( &(*tree)->left, item);
else
return searchElement( &(*tree)->right, item);
}
int BST :: findSmallestNode(node *tree){
if( tree==NULL || tree->left==NULL)
return (tree->data);
else
findSmallestNode( tree->left);
}
node * find_Insucc(node *curr)
{
node *succ=curr->right;
if(succ!=NULL){
while(succ->left!=NULL).
succ=succ->left;
}
return(succ);
}
int BST :: findLargestNode(node *tree){
if( tree==NULL || tree->right==NULL)
return (tree->data);
else
findLargestNode(tree->right);
}
void BST :: deleteNode(int item){
node *curr=tree,*succ,*pred;
int flag=0,delcase;
while(curr!=NULL && flag!=1)
{
if(item < curr->data){
pred = curr;
curr = curr->left;
}
else if(item > curr->data){
pred = curr;
curr = curr->right;
}
else{
flag=1;
}
}
if(flag==0){
cout<<"\nItem does not exist : No deletion\n";
getch();
goto end;
}
if(curr->left==NULL && curr->right==NULL)
delcase=1;
else if(curr->left!=NULL && curr->right!=NULL)
delcase=3;
else
delcase=2;
if(delcase==1){
if(pred->left == curr)
pred->left=NULL;
else
pred->right=NULL;
delete(curr);
}
if(delcase==2){
if(pred->left==curr){
if(curr->left==NULL)
pred->left=curr->right;
else
pred->left=curr->left;
}
else{
if(curr->left==NULL)
pred->right=curr->right;
else
pred->right=curr->left;
}
delete(curr);
}
if(delcase==3){
succ = find_Insucc(curr);
int item1 = succ->data;
deleteNode(item1);
curr->data = item1;
}
end:
}
void main(){
textmode(C80);
BST obj;
int choice;
int height=0,total=0,largest=0,smallest=0,n,item;
node **tmp;
textbackground(4);
textcolor(14);
while(1){
clrscr();
printf("\n ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿\ n");
printf(" ³");
textcolor(0);
cprintf(" All function of Binary Search Tree ");
textcolor(14);
printf("³\n");
printf(" ÃÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´ \n");
printf(" ³1³ Creat New Tree ³\n");
printf(" ÃÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´ \n");
printf(" ³2³ Travesal (Inorder,Preorder,Postorder)³\n");
printf(" ÃÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´ \n");
printf(" ³3³ Information your tree about ³\n");
printf(" ÃÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´ \n");
printf(" ³4³ Insert Node ³\n");
printf(" ÃÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´ \n");
printf(" ³5³ Serach Node ³\n");
printf(" ÃÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´ \n");
printf(" ³6³ Find Smallest & Largest Node ³\n");
printf(" ÃÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´ \n");
printf(" ³7³ Delete Node ³\n");
printf(" ÃÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´ \n");
printf(" ³8³ Exit ³\n");
printf(" ÀÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\ n");
textcolor(0);
cprintf(" Select >>> ");
cin>>choice;
textcolor(14);
if (choice > 8 || choice<1)
{
textcolor(139);
cprintf("\n\n Warning : Select is incorrect (1-8) ");
getch();
}
textcolor(14);
switch(choice){
case 1 :
cout<<"\n How many nodes you want to creat : ";
cin>>n;
cout<<"\n";
for(int i=0;i<n;i++){
cout<<" :: Enter value "<<i+1<<" : ";
cin>>item;
obj.createTree(&obj.tree,item);
}
break;
case 2 :
cout<<"\n\n Inorder Traversal : ";
obj.inOrder(obj.tree);
cout<<"\n\n Pre-order Traversal : ";
obj.preOrder(obj.tree);
cout<<"\n\n Post-order Traversal : ";
obj.postOrder(obj.tree);
getch();
break;
case 3 :
printf(" ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿\n");
obj.determineHeight(obj.tree,&height);
printf(" ³ Hieght Nodes : %5d ³\n",height);
printf(" ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´\n");
total=obj.totalNodes(obj.tree);
printf(" ³ Total Nodes : %5d ³\n",total);
printf(" ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´\n");
total=obj.internalNodes(obj.tree);
printf(" ³ Internal Nodes : %5d ³\n",total);
printf(" ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´\n");
total=obj.externalNodes(obj.tree);
printf(" ³ External Nodes : %5d ³\n",total);
printf(" ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\n");
getch();
break;
case 4 :
cout<<"\n Enter value : ";
cin>>item;
obj.createTree(&obj.tree,item);
textcolor(139);
cprintf("\n This item is inserted ");
getch();
textcolor(14);
break;
case 5 :
cout<<"\n\n Enter item for search : ";
cin>>item;
&(*tmp) = obj.searchElement(&obj.tree,item);
textcolor(139);
if( (*tmp) == NULL)
cprintf("\n Search Item Not Found ");
else
cprintf("\n Search Item was Found ");
getch();
textcolor(14);
break;
case 6 : /
printf(" ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿\n");
printf(" ³ Largest Node : %7d ³\n",obj.findLargestNode(obj.tree));
printf(" ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´\n");
printf(" ³ Smallest Node : %7d ³\n",obj.findSmallestNode(obj.tree));
printf(" ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\n");
getch();
break;
case 7 :
cout<<"\n\n--Deleting a Node from a tree--\n";
cout<<"Enter value : ";
cin>>item;
obj.deleteNode(item);
break;
case 8 : exit(1);
}
}
}