Двоичное дерево поиска?

Question

Я пытаюсь создать двоичное дерево поиска с помощью C++. Я использую только функции для вставки данных и поиска данных. Кажется, я не могу заставить программу работать, хотя я считаю, что она очень логична и правильна?

Любая помощь была бы принята с благодарностью.

#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

В searchForItem

if(current->data > toFindNum) 

не это должно быть:

if (toFindNum > current->data) 

Answer 2

Одна из проблем здесь.

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

Рассмотрите это дерево.

5 
/\ 
4 6 

Вашего toFindNum равно 4. Если current->data 5, больше, чем 4, вы должны смотреть в левом ребенке, а не прямо один.

Ваше заявление должно быть таким.

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