Arbre de recherche binaire?

Question

J'essaie de faire un arbre de recherche binaire en utilisant C++. J'utilise seulement les fonctions pour insérer des données et trouver des données. Je n'arrive pas à faire fonctionner le programme, même si je trouve que c'est très logique et correct?

Toute aide serait grandement appréciée.

#include<iostream> 
using namespace std; 

template <class T> 
class BinarySearchTree 
{ 
private: 
    struct tree 
    { 
     tree *leftchild; 
     tree *rightchild; 
     T data; 
    }; 
    tree *root; 
public: 
    BinarySearchTree() 
    { 
     root=NULL; 
    } 
    void insert(T); 
    void searchForItem(T); 
}; 

template<class T> 
void BinarySearchTree<T>::insert(T newNum) 
{ 
    tree *newItem = new tree; 
    tree *parent; 

    newItem->data = newNum; 
    newItem->leftchild = NULL; 
    newItem->rightchild = NULL; 

    if(root==NULL) 
     root=newItem; 

    else 
    { 
     tree *current; 
     current=root; 
     while(current) 
     { 
      parent = current; 

      if(newItem->data > current->data) 
       current = current->rightchild; 
      else 
       current = current->leftchild; 
     } 

     if(newItem->data > parent->data) 
      parent->rightchild = newItem; 
     else 
      parent->leftchild = newItem; 
    } 

} 

template<class T> 
void BinarySearchTree<T>::searchForItem(T toFindNum) 
{ 
    tree *current; 
    tree *parent; 

    current = root; 
    if(current->data == toFindNum) 
     cout<<toFindNum<<" is the root of this binary search tree."<<endl; 

    while(current->data != toFindNum) 
    { 
     parent = current; 

     if(current->data > toFindNum) 
      current = current->rightchild; 
     else 
      current = current->leftchild; 
    } 

    cout<<toFindNum<<" is the child of "<<parent->data<<endl; 
} 
int main() 
{ 
    BinarySearchTree<int> b; 

    b.insert(5); 
    b.insert(4); 
    b.insert(3); 
    b.insert(2); 
    b.insert(7); 

    b.searchForItem(4); 
} 

Answer 1

Dans searchForItem

if(current->data > toFindNum) 

ne doit pas être que:

if (toFindNum > current->data) 

Answer 2

Un problème est ici.

if(current->data > toFindNum) 
    current = current->rightchild; 

Considérons cet arbre.

5 
/\ 
4 6 

Votre toFindNum est 4. Si current->data est 5, supérieur à 4, vous devez regarder dans l'enfant gauche, pas un droit.

Votre déclaration devrait être ceci.

if(current->data > toFindNum) 
    current = current->leftchild; 
else 
current = current->rightchild;