#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);
}
Back to top
elinaz
مهمون يكي دو روزه
Joined: 21 Nov 2007
Posts: 42
Location: تهران
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);
}
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-
");
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
Back to top
elinaz
مهمون يكي دو روزه
Joined: 21 Nov 2007
Posts: 42
Location: تهران
Posted: Tue Dec 11, 2007 9:22 pm Post subject: قسمت پاياني برنامه
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
يك پروژه انجام شده مر بو ط به درختها
پاسخ با نقل قول
