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 );
}
Posted: Tue Dec 11, 2007 9:21 pm Post subject: ادامه برنامه
//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);
}
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");
if (choice > 8 || choice<1)
{
textcolor(139);
cprintf("\n\n Warning : Select is incorrect (1- ");
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;
//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
از کتاب بفرماييد يک فنجان چاي:
بدون که هر کلمه و تقاضاي خودت را به دسته ناشناخته بسپار و هر چه را پيش مي آيد بپذير خدا هر طور که مي سازدت همانطور باش و اگر مي شکندت شکستن را بپذير
بدان كه در همه حال خدا با توست
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum