Arbre de recherche binaire utilisant des classes

Question

J'ai essayé d'implémenter l'arborescence de recherche binaire en utilisant des classes. Chaque fois que j'essaie de compiler et d'exécuter le programme, le programme se termine. J'ai essayé beaucoup de choses comme faire le * root public pour y accéder en main afin que je puisse mettre à jour la racine, mais de toute façon il devient nul à chaque fois. L'aide sera appréciée. Ceci est pour mon projet d'université.

#include <iostream> 
using namespace std; 
class tree; 
class Node { 
    friend class tree; 
private: 
    Node *lchild,*rchild; 
    int data; 
public: 
    Node (int x) { 
     data = x; 
     lchild = rchild = NULL; 
    } 
}; 
class tree { 
protected: 
    Node* root; 
    void inorder(const Node* root)const; 
public: 
    tree() { 
     root = NULL; 
    } 
    bool insert(int item); 
    void inorder() const {inorder(root);}; 
    Node* getroot() { 
     return root; 
    } 
}; 
bool tree :: insert(int item) { 
    if (root == NULL) { 
     Node *temp = new Node(item); 
     root = temp; 
     return (bool) root; 
    } 
    if (item < root -> data) { 
     insert(item); 
    } 
    if (item > root -> data) { 
     insert(item); 
    } 
    else if (item == root -> data) { 
     cout<<"Duplicate"; 
     exit (0); 
    } 
    return (bool) root; 
} 
void tree :: inorder(const Node *root)const { 
    if (root != NULL) { 
     inorder(root -> lchild); 
     cout<<root -> data; 
     inorder(root -> rchild); 
    } 
} 
int main() 
{ 
    tree obj1; 
    obj1.insert(3); 
    //obj1.insert(4); 
    obj1.insert(1); 
    //obj1.insert(5); 
    obj1.inorder(); 
} 

Answer 1

La raison pour laquelle root obtient NULL encore et est à nouveau qu'il change en fait jamais sa valeur à quelque chose d'autre que NULL. Peut-être avez-vous introduit ce comportement dans votre code lors de la résolution d'autres problèmes; cependant vous affectez root=NULL dans le constructeur; ensuite, vous affectez uniquement obj.root1 = ..., tandis que vous renvoyez root dans getroot() { return root; }. En outre, vous passez Node *root en tant que paramètre dans votre fonction d'insertion; Notez que cette variable locale nommée root masque le membre de données root, de sorte que root->... dans ces fonctions adressera toujours la variable locale et non le membre de données. Avant de plonger dans le code dont l'interface a besoin d'une refonte, je suggère d'adapter le design, puis d'adapter le code; Je suis sûr que les erreurs disparaîtront tout simplement. Je suggère d'adapter l'interface de class tree comme suit et écrire le code autour d'elle. La fonction membre inorder() doit être const pour indiquer qu'elle ne modifie pas l'état de l'objet. Notez que les fonctions const -member peuvent, contrairement à d'autres fonctions membres non statiques, être appelées const -objects.

class Node { 
    friend class tree; 
private: 
    Node *lchild,*rchild; 
    int data; 
public: 
    Node (int x) { 
     data = x; 
     lchild = rchild = NULL; 
    } 
}; 
class tree { 
public: 
    tree() { root = NULL; } 
    bool insert(int item) { return insert(item,root); }; 
    void inorder() const { inorder(root);}; 

protected: 
    Node* root; 
    void inorder(const Node* curr) const; 
    bool insert(int item, Node* curr); 

}; 

bool tree :: insert(int item, Node *currNode) { 
    if (root == NULL) { 
     root = new Node(item); 
     return true; 
    } 
    else if (item < currNode->data) { 
     if (currNode->lchild == NULL) { 
      currNode->lchild = new Node(item); 
      return true; 
     } 
     else { 
      return insert(item, currNode->lchild); 
     } 
    } 
    else if (item > currNode->data) { 
     if (currNode->rchild == NULL) { 
      currNode->rchild = new Node(item); 
      return true; 
     } 
     else { 
      return insert(item, currNode->rchild); 
     } 
    } 
    else // item == currNode->data 
     return false; // duplicate; do not insert 
}