一个简单的二叉搜索树的实现

上一篇文章简单实现了一个普通的二叉树，参见这里。

二叉搜索树是二叉树的一种变体，它相比普通二叉树的特性就是里面的数据都是有序的，中序遍历它就可以得到一个升序数组。

BSTreet实现代码如下：

#pragma once

#include<iostream>
using namespace std;

template<typename T>
struct BSTreeNode
{
    T _data;
    BSTreeNode<T>* _left;
    BSTreeNode<T>* _right;
    BSTreeNode(const T& t=T())
        :_data(t)
         ,_left(NULL)
         ,_right(NULL)
    {}
};

template<typename T>
class BSTree
{
    typedef BSTreeNode<T> Node;
public:
    BSTree()
        :_root(NULL)
    {}

    bool insert(const T& t)
    {
        Node* s=new Node(t);
        if(_root==NULL)
        {
            _root=s;
            return true;
        }
        else
        {
            Node* father=NULL;
            Node* cur=_root;
            while(cur!=NULL)
            {
                if(cur->_data==s->_data)
                    return false;
                if(cur->_data<s->_data)
                {
                    father=cur;
                    cur=cur->_right;
                }
                else
                {
                    father=cur;
                    cur=cur->_left;
                }
            }
            if(father->_data<s->_data)
                father->_right=s;
            else
                father->_left=s;
            return true;
        }
    }

    void InOrder()
    {
        _InOrder(_root);
        cout<<endl;
    }

protected:
    void _InOrder(Node* root)
    {
        if(root==NULL)
            return;
        _InOrder(root->_left);
        cout<<root->_data<<" ";
        _InOrder(root->_right);
    }

private:
    Node* _root;
};

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在 github 上：点我前往