ParsX.com

elinaz

يك پروژه انجام شده مر بو ط به درختها

قبل از گذاشتن برنامه از مسولين سايتي كه اين برنامه را گذاشته بودند تا دانشجويان از آن استفاده كنند معذرت مي خوام كه منبع را فراموش كردم

اين برنامه تمام اعمال مربوط به ايجاد درخت (Tree) , پیمایش درخت بصورت inorder , preorder postorder و جستجوی باینری با استفاده از ليست پيوندي مي باشد

elinaz · Posted: Tue Dec 11, 2007 9:19 pm Post subject: برنامه

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

elinaz · 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- Cool

");
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

elinaz

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

elinaz · Posted: Tue Dec 11, 2007 9:28 pm Post subject: !!!!!!

اگر برايتان اين برنامه به دليل برعكس شدن علايم ناخوانا بود

ميل بزنيد تا فايل اصلي را برايتان ارسال كنم

-----------------------------------------------------------------------------------------

از کتاب بفرماييد يک فنجان چاي:
بدون که هر کلمه و تقاضاي خودت را به دسته ناشناخته بسپار و هر چه را پيش مي آيد بپذير خدا هر طور که مي سازدت همانطور باش و اگر مي شکندت شکستن را بپذير
بدان كه در همه حال خدا با توست