二叉搜索树？

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

这里有一个问题.

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;