Arbres de recherche binaire

Question

J'ai une question concernant l'implémentation de l'arbre de recherche binaire en C++. Voici la question ci-dessous

Implémentez un BST simple (non basé sur un modèle) qui stocke des entiers. Fournissez les opérations suivantes: insertion, suppression, traversée inOrder, traversée preOrder, traversée postOrder.

Utilisez des routines récursives pour gérer l'arborescence.

Le traitement d'un noeud implique simplement l'impression du contenu du noeud, qui dans ce cas est l'entier stocké dans le noeud.

Les données doivent provenir de fichiers de test. Le programme principal doit ouvrir le fichier de données et l'insérer dans l'arborescence et faire la démonstration d'autres opérations arborescentes.

Le but de cet exercice est de démontrer que vous comprenez le BST. Il n'est pas nécessaire d'aller trop loin et de mettre en place des opérations non demandées.

J'ai seulement créé le fichier Header jusqu'à présent. Quelqu'un pourrait-il s'il vous plaît jeter un oeil et conseiller si je me dirige dans la bonne direction?

using namespace std; 
#ifndef BSTNODE_H 
#define BSTNODE_H 
class BSTNode 
{ 
    private: 
    //Defines the 'node' structure 
    struct tree_node 
    { 
    tree_node *left; // left subtree has smaller elements 
    tree_node *right; // right subtree has larger elements 
    int m_data; 
    }; 
    //root * r; 
    public: 
     //The Constructor 
     BSTNode(); 
     //The Destructor 
     ~BSTNode(); 
     //Inserts a value into a BST, public function 
     void insert(const m_data & d); 
     //Removes a value from a BST, public function 
     void remove(const m_data & d); 
     //isEmpty function, public function 
     bool isEmpty(); 
     BSTNode getData(); 
     void inOrder(const m_data & d); 
     void preOrder(const m_data & d); 
     void postOrder(const m_data & d); 
}; 
#endif 

Ensuite, je dois créer le fichier BSTNode.cpp. Appréciez votre réponse par courrier à jediknight80n@hotmail.com Merci d'avance.

Answer 1

Vous semblez avoir oublié de typedef le type m_data que vous utilisez dans les différentes méthodes, et je ne comprends pas pourquoi vous voulez une struct tree_node séparée (plutôt que d'utiliser la classe elle-même?) Ni pourquoi getData Devrais- Renvoie BSTNode plutôt que int.

Answer 2

//Inserts a value into a BST, public function 
    void insert(const m_data & d); 
    //Removes a value from a BST, public function 
    void remove(const m_data & d); 
    //isEmpty function, public function 
    bool isEmpty(); 
    BSTNode getData(); 
    void inOrder(const m_data & d); 
    void preOrder(const m_data & d); 
    void postOrder(const m_data & d); 

m_data est un membre, pas un type. Vous devriez utiliser int ici. En outre, puisque votre noeud est tree_node, la classe externe devrait probablement représenter l'arbre dans son ensemble (c'est-à-dire, BSTree pas BSTNode).

Également 'using namespace std;' est mauvais dans les en-têtes, car il le force sur tout ce qui inclut l'en-tête sans aucun moyen de se retirer. Si vous l'utilisez, je vous recommande de le conserver dans des fichiers .cpp.

Answer 3

C'est une question classique sur les BST - tout bon livre sur les structures de données vous donnerait le code entier. La page suivante contient des exemples de code pour C++ http://cslibrary.stanford.edu/110/BinaryTrees.html.

Les fonctions Traversal ne doivent pas faire partie de la classe BST elle-même, en effet le BSTNode doit exposer les pointeurs de nœud gauche/droit - et l'application appelante doit l'appeler de la manière particulière. Ou utilisez une fonction de rappel et fournissez le code de traversée dans votre classe, de cette façon, ce serait beaucoup plus propre.

Answer 4

couple de choses - comme d'autres l'ont souligné, vous devrez utiliser

void insert(const int & d); 
//Removes a value from a BST, public function 
void remove(const int & d); 
//isEmpty function, public function 
bool isEmpty(); 
BSTNode getData(); 
void inOrder(const int & d); 
void preOrder(const int & d); 
void postOrder(const int & d); 

Les autres est que vous avez commenté votre nœud racine. Bien que vous l'ayez défini incorrectement, vous devrez inclure un noeud racine dans la classe.La définition correcte serait

tree_node *root; 

En outre, comme l'a souligné avant, retirer le

using namespace std;

à partir du fichier d'en-tête et de le placer dans votre fichier d'implémentation à la place.

C'est tout ce que je peux voir maintenant.

Answer 5

Un autre problème est que la classe comme spécifié déclare un type imbriqué, et les méthodes, mais aucune donnée membres.

---

Vous pouvez déclarer la fonctionnalité de traversée en utilisant des itérateurs: par ex. la méthode de pré-commande renvoie un interac- teur, que vous pouvez déréférencer vers un noeud, ou incrémenter pour pointer vers le noeud suivant dans la séquence de précommande. Ou bien, vous pouvez déclarer la fonctionnalité de traversée en utilisant des rappels: l'appelant passe une instance de rappel à la méthode de précommande, la méthode de précommande traverse l'arbre et appelle la méthode de rappel pour chaque nœud: la méthode de rappel prend un nœud , plus spécifiquement, les données de noeud) en tant que paramètre, et pourrait renvoyer un booléen qui laisserait le callback spevify qu'il veut abend le traversal.

Answer 6

J'ajouterais aussi une méthode de recherche.

bool search(int whatIlookfor); 

ou mieux encore

tree_node* search(int whatIlookfor); 

De plus, gardez tree_node *root dans un endroit sûr.

Answer 7

quelque chose de trivial:

tree_node *left; // left subtree has smaller elements 

En général, sous-arbre gauche contient également les éléments égaux.

Answer 8

• à l'aide des pointeurs gauche et à droite du type struct dans votre exemple, limiterait flexibilty - suppose que je prends votre BST et de passage à l'enfant à gauche de la racine, et que vous souhaitez appeler des opérations sur ce nouveau sous-arbre. Je ne peux pas puisque les pointeurs sont du type struct. Je suggère plutôt d'utiliser les deux pointeurs de type BSTNode.

  BSTNode *left;

  BSTNode *right;

  Cela permettrait également de résoudre votre problème racine (pas de pointeur racine explicite requis), étant donné que le pointeur que vous utilisez pour référencer votre objet principal, pointera vers la racine de toute façon.

• Les fonctions traversal ne devraient pas exiger des arguments, quand ils traversent essentiellement l'arbre entier et imprimer tous les éléments de données le long. L'élément de données peut être transmis à une autre fonction de membre de recherche pour rechercher sa position comme indiqué par TrueStar.

• Je suggère également quelques fonctions de membres privé pour réduire la complexité de vos fonctions membres publiques (DeleteNodeCaseB(int data) appelleraient DeleteNodeCaseA(int data) à partir dans le temps et encore) -

  BSTNode * setleft(int data);

  BSTNode * setright(int data);

  void DeleteNodeCaseA(int data)/* soit ou les deux enfants gauche et droit n'existent pas */

  void DeleteNodeCaseB(int data)/* a deux enfants gauche et à droite */

Answer 9

Puisque vous utilisez C++, vous voudrez peut-être envisager d'utiliser des bibliothèques standard au lieu d'essayer de mettre en œuvre vous-même? Les bibliothèques STL sont livrées avec un arbre rouge-noir, ce qui peut mieux convenir à votre application. Les arbres binaires peuvent être tronqués ou dégénérés dans une liste de liens. PS: Bien sûr, cela suppose que vous ne faites pas une tâche de devoirs.