برنامه ايجاد درخت و اعمال مقدماتي ان ديدن اون ضرر نداره

/*
::::::>>>>>>> All function for Binary Search Tree <<<<<<<::::::
# #
# Programmer : Pezhman Roudkhaneei #
# Student of Islamic Azad University #
# (Branch of Lahijan) #
# Course : M.S #
# Unit Name : Data Structure #
# Professor Name : Dr.Shafoori #
# #
# Date >>>> 2005/06/29 , (84/4/8) #
# #
# WWW : [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ] & [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ] #
# E-mail : [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ] #
# #
# Programed for Turbo C++ 3.0 #
# #
################################################## ##############
*/

#include <iostream.h>
#include <process.h> //for exit(1)
#include <conio.h>
#include <graphics.h>
#include <stdio.h>
#include <stdlib.h>
#include <process.h>

struct node{ //Define structure
struct node *left;
int data;
struct node *right;
};

class BST{ // Define Class For Binary Search Tree (BST)
public:
node * tree;
void createTree(node **,int item); // Define Building Tree
void preOrder(node *); // Define PreOrder Function
void inOrder(node *); // Define InOrder Function
void postOrder(node *); // Define PostOrder Function

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;
}

};

// Body of CreatTree Function , This Functon Creat New Tree
// This Function is kind of recersive.
void BST :: createTree(node **tree,int item)
{ //Start
if(*tree == NULL) // if tree = NULL
{ *tree = new node;
(*tree)->data = item;
(*tree)->left = NULL;
(*tree)->right = NULL;
}
else // if( !tree= NULL) or if
{
if( (*tree)->data > item)
createTree( &((*tree)->left),item);
else // if( (*tree)->data < item)
createTree( &((*tree)->right),item);
}
} //End of creatTree Function

// This function is for Preorder travesal.
void BST :: preOrder(node *tree){
if( tree!=NULL){
cout<<" "<< tree->data;
preOrder(tree->left);
preOrder(tree->right);
}
}

// This function is for Inorder travesal.
void BST :: inOrder(node *tree){
if( tree!=NULL){
inOrder( tree->left);
cout<<" "<< tree->data;
inOrder(tree->right);
}
}

// This function is for Postorder travesal.
void BST :: postOrder(node *tree){
if( tree!=NULL){
postOrder( tree->left);
postOrder( tree->right);
cout<<" "<<tree->data;
}
}

// This fuction return tree hight .
void BST :: determineHeight(node *tree, int *height){
int left_height, right_height;
if( tree == NULL) // if tree = Null
*height = 0;
else{ // if ( !tree=NULL )
determineHeight(tree->left, &left_height);
determineHeight(tree->right, &right_height);
if( left_height > right_height)
*height = left_height + 1;
else // if (right_heigh t> left_height)
*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);
//return (tree->data);
}


//Finding In_order Successor of given node..
//for Delete Algo.
node * find_Insucc(node *curr)
{
node *succ=curr->right; //Move to the right sub-tree.
if(succ!=NULL){
while(succ->left!=NULL) //If right sub-tree is not empty.
succ=succ->left; //move to the left-most end.
}
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;
//step to find location of node
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{ //curr->data = item
flag=1;
}
}

if(flag==0){
cout<<"\nItem does not exist : No deletion\n";
getch();
goto end;
}

//Decide the case of deletion
if(curr->left==NULL && curr->right==NULL)
delcase=1; //Node has no child
else if(curr->left!=NULL && curr->right!=NULL)
delcase=3; //Node contains both the child
else
delcase=2; //Node contains only one child


//Deletion Case 1
if(delcase==1){
if(pred->left == curr) //if the node is a left child
pred->left=NULL; //set pointer of its parent
else
pred->right=NULL;
delete(curr); //Return deleted node to the memory bank.
}

//Deletion Case 2
if(delcase==2){
if(pred->left==curr){ //if the node is a left child
if(curr->left==NULL)
pred->left=curr->right;
else
pred->left=curr->left;
}
else{ //pred->right=curr
if(curr->left==NULL)
pred->right=curr->right;
else
pred->right=curr->left;
}
delete(curr);
}

//Deletion case 3
if(delcase==3){
succ = find_Insucc(curr); //Find the in_order successor
//of the node.
int item1 = succ->data;
deleteNode(item1); //Delete the inorder successor
curr->data = item1; //Replace the data with the data of
//in order successor.
}
end:
}

// Main Body
void main(){
textmode(C80); //For Change Text Mode
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 : // For Create Tree
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 : // All Traversals (Inorder - Preorder - Postorder)
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");
//Determining Height of Tree
obj.determineHeight(obj.tree,&height);

printf(" ³  Hieght Nodes : %5d ³\n",height);
printf(" أؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤ ؤؤؤؤؤؤؤؤؤؤؤؤؤ´\n");

//Total nodes in a tree
total=obj.totalNodes(obj.tree);

printf(" ³  Total Nodes : %5d ³\n",total);
printf(" أؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤ ؤؤؤؤؤؤؤؤؤؤؤؤؤ´\n");
//Internal nodes in a tree
total=obj.internalNodes(obj.tree);
printf(" ³  Internal Nodes : %5d ³\n",total);
printf(" أؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤ ؤؤؤؤؤؤؤؤؤؤؤؤؤ´\n");
//External nodes in a tree
total=obj.externalNodes(obj.tree);
printf(" ³  External Nodes : %5d ³\n",total);
printf(" ہؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤؤ ؤؤؤؤؤؤؤؤؤؤؤؤؤظ\n");

getch();
break;

case 4 : //Inserting a node in a tree
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 : //Search element

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 : //Find Largest & Smallest Node

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 : //Deleting a node from a tree
cout<<"\n\n--Deleting a Node from a tree--\n";
cout<<"Enter value : ";
cin>>item;
obj.deleteNode(item);
break;

case 8 : exit(1);

}//End of switch
}
}// End of Main body
//End of program