二叉搜索树也是二叉树，不过多了一些限定，根节点值大于左子树小于右子树，子树递归定义。

/**************************************************author:周翔*e-mail:604487178@qq.com*blog:http://blog.csdn.net/zhx6044***************************************************/#ifndef BINARYSEARCHTREE_HPP#define BINARYSEARCHTREE_HPP#include 
    
     #include "linkQueue.hpp"template 
     
      /** * @brief The BinarySearchTree class 二叉搜索树 */class BinarySearchTree{public:    BinarySearchTree();    ~BinarySearchTree();    bool find(const T &t) const;    void insert(const T &t);    void remove(const T &t);    void clear();    bool isEmpty() const;    void levelTraverse(std::ostream &os = std::cout) const;private:    struct node {        T data;        node *lc, *rc;        node():lc(NULL),rc(NULL) {        }        node(const T &t, node *_lc = NULL, node *_rc = NULL):            data(t),            lc(_lc),            rc(_rc) {        }    };    node *root;    void clear(node *p);    void insert(const T &t, node *&p);//此处为指针引用，因为改变指向的值，不只是使用指针指向的值    bool find(const T &t, node *p) const;    void remove(const T &t, node *&p);//};template 
      
       inlineBinarySearchTree
       
        ::BinarySearchTree():root(NULL){}template 
        
         BinarySearchTree
         
          ::~BinarySearchTree(){ clear();}template 
          
           bool BinarySearchTree
           
            ::find(const T &t) const{ return find(t,root);}template 
            
             /** * @brief BinarySearchTree
             
              ::insert 插入操作 * @param t */void BinarySearchTree
              
               ::insert(const T &t){ insert(t,root);}template 
               
                void BinarySearchTree
                
                 ::remove(const T &t){ remove(t,root);}template 
                 
                  void BinarySearchTree
                  
                   ::clear(){ if(isEmpty()) { } else { clear(root); root = NULL; }}template 
                   
                    void BinarySearchTree
                    
                     ::clear(node *p){ if (p->lc != NULL) { clear(p->lc); } if (p->rc != NULL) { clear(p->rc); } delete p;}template 
                     
                      inlinebool BinarySearchTree
                      
                       ::isEmpty() const{ return root == NULL;}template 
                       
                        void BinarySearchTree
                        
                         ::insert(const T &t, node *&p){ if (p == NULL) { p = new node(t); } else { if (t < p->data) { insert(t,p->lc); } else { insert(t,p->rc); } }}template 
                         
                          bool BinarySearchTree
                          
                           ::find(const T &t, node *p) const{ bool re = false; if (p == NULL) { } else { if (t < p->data) { re = find(t,p->lc); } else { if (t > p->data) { re = find(t,p->rc); } else { re = true; } } } return re;}template 
                           
                            void BinarySearchTree
                            
                             ::remove(const T &t, node *&p)//在处理关系时看成线，在处理值时p看成点，线向下指向的点，{ if (p == NULL) { } else { if (t == p->data) { if (p->lc != NULL && p->rc != NULL) {//两个子节点 node *q = p->rc; while (q->lc != NULL) q = q->lc;//右子树最左的节点也就是右子树最小节点代替根节点 p->data = q->data;//节点值改变就行 remove(q->data,p->rc);//在右子树中删除替换的节点 } else { if (p->lc == NULL || p->rc == NULL) {//一个子节点 node *q = p; p = (p->lc != NULL) ? p->lc : p->rc; delete q; } else { delete p; p = NULL; } } } else { if (t < p->data) { remove(t,p->lc); } else { remove(t,p->rc); } } }}template 
                             
                              void BinarySearchTree
                              
                               ::levelTraverse(std::ostream &os) const{ LinkQueue
                               
                                 queue; queue.enqueue(root); while(!queue.isEmpty()) { node *t = queue.dequeue(); if (t != NULL) { os << t->data << " "; queue.enqueue(t->lc); queue.enqueue(t->rc); } }}#endif // BINARYSEARCHTREE_HPP