0
j'ai mettre en œuvre l'arbre de recherche binaire en C++arbre recherche binaire
#include <iostream>
#include <cstdlib>
using namespace std;
class binary{
private:
struct tree{
tree *left;
tree *right;
int data;
};
tree *root;
public:
binary(){
root=NULL;
}
bool empty() { return root=NULL;}
void print_inorder();
void inorder(tree*);
void print_preorder();
void pre_order(tree*);
void print_postorder();
void post_order(tree *);
void insert(int);
void remove(int);
};
void binary::insert(int d){
tree *t=new tree;
tree *parent;
t->data=d;
t->left=NULL;
t->right=NULL;
parent=NULL;
//is new tree;
if (empty()) root=t;
else{
tree *current;
current=root;
//find Nod's parent
while (current){
parent=current;
if (t->data>current->data) current=current->right;
else current=current->left;
}
if (t->data<parent->data)
parent->left=t;
else
parent->right=t;
}
}
void binary::remove(int d){
//locate the element
bool found=true;
if (empty()){
cout<<"tree is empty"<<endl;
return ;
}
tree *current;
tree *parent;
current=root;
while (current!=NULL){
if (current->data==d){
found=true;
break;
}
else{
parent=current;
if (d>current->data) current=current->right;
else current=current->left;
}
}
if (!found){
cout<<"data not found "<<endl;
return ;
}
//three case
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children
// Node with single child
if ((current->left==NULL && current->right!=NULL )||(current->left!=NULL && current->right==NULL)){
if (current->left==NULL && current->right!=NULL){
if(parent->left==current){
parent->left=current->right;
delete current;
}
else{
parent->right=current->right;
delete current;
}
}
else // left child present, no right child
{
if (parent->left==current){
parent->left=current->left;
delete current;
}
else{
parent->right=current->left;
delete current;
}
}
return ;
}
if (current->left==NULL && current->right==NULL){
if (parent->left==current) parent->left=NULL;
else parent->right==NULL;
delete current;
return ;
}
//node with 2 children
//replace node with smalles value in right subtree
if ( current->left!=NULL && current->right!=NULL){
tree *ch;
ch=current->right;
if ((ch->left==NULL) &&(ch->right==NULL))
{
current=ch;
delete ch;
current->right=NULL;
}
else// right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if ((current->right)->left!=NULL){
tree * rr;
tree * lr;
lr=current->right;
rr=(current->right)->left;
while (rr->left!=NULL){
lr=rr;
rr=rr->left;
}
current->data=rr->data;
delete rr;
lr->left=NULL;
}
else
{
tree *tmp;
tmp=current->right;
current->data=tmp->data;
current->right=tmp->right;
delete tmp;
}
}
return;
}
}
void binary::print_inorder(){
inorder(root);
}
void binary::inorder(tree *p){
if (p!=NULL){
if (p->left) inorder(p->left);
cout<<" "<<p->data<<" ";
if (p->right) inorder(p->right);
}
else return ;
}
void binary::print_preorder(){
pre_order(root);
}
void binary::pre_order(tree *p){
if (p!=NULL){
cout<<" "<<p->data<<" ";
if (p->left) pre_order(p->left);
if (p->right) pre_order(p->right);
}
else return ;
}
void binary::print_postorder(){
post_order(root);
}
void binary::post_order(tree *p){
if (p!=NULL){
if (p->left) post_order(p->left);
if (p->right) post_order(p->right);
cout<<" "<<p->data;
}
else return ;
}
int main(){
binary b;
int ch,tmp,tmp1;
while (1){
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Insertion/Creation "<<endl;
cout<<" 2. In-Order Traversal "<<endl;
cout<<" 3. Pre-Order Traversal "<<endl;
cout<<" 4. Post-Order Traversal "<<endl;
cout<<" 5. Removal "<<endl;
cout<<" 6. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1: cout<<"enter number to be inserted:";
cin>>tmp;
b.insert(tmp);
break;
case 2: cout<<endl;
cout<<"in order traversal"<<endl;
cout<<"------------------"<<endl;
b.print_inorder();
break;
case 3: cout<<endl;
cout<<"pre order traversal "<<endl;
cout<<"------------------"<<endl;
b.print_preorder();
break;
case 4: cout<<endl;
cout<<"post order traversal"<<endl;
cout<<"---------------------"<<endl;
b.print_postorder();
break;
case 5: cout<<"enter data to be deleted:";
cin>>tmp1;
b.remove(tmp1);
break;
case 6:
return 0;
}
}
return 0;
}
il compile très bien mais problème est le suivant: quand j'entrer dans le choix 1 il dire entrer le numéro à insérer i entrer par exemple 7 et le programme dit :
binary_tree exe has stopped working
windows can check online for a solution to the problem
check online for a solution and close program
close program
Pourquoi? Quelle est la raison de ce type de problème?
C'est ce qui vous aidera à passer au travers d'un débogueur, au lieu de nous faire corriger votre code par des bogues. – Joe