#ifndef BST_H_INCLUDED
#define BST_H_INCLUDED
template <class T>
class treenode
{
public:
    treenode():lson(NULL),rson(NULL),freq(1){};
    T data;
    int freq;
    treenode *lson;
    treenode *rson;
};
template <class T>
class bst
{
private:
    treenode<T>*root;
    void insertpri(treenode<T>*&node,T x);
    treenode <T>*findpri(treenode<T>*node,T x);
    void insubtree(treenode<T>*node);
    void deletepri(treenode<T>*&node,T x);
public:
    bst():root(NULL){}
    void insert_(T x);
    treenode<T>*find_(T x);
    void delete_(T x);
    void traversal();
};

#endif // BST_H_INCLUDED



#include "bst.h"

template <class T>
void bst<T>::insertpri(treenode<T>*&node,T x)
{
    if (node==NULL)
    {
        node=new treenode<T>();
        node->data=http://www.mamicode.com/x;
        return;
    }
    if (node->data>x)
    {
     insertpri(node->lson,x);
    }
    else if (node->data<x)
    {
        insertpri(node->rson,x);
    }
    else (node->freq)++;
}

template <class T>
void bst<T>::insert_(T x)
{
    insertpri(root,x);
}

template <class T>
treenode<T>* bst<T>::findpri(treenode<T>*node,T x)
{
    if (node==NULL)
    {
        return NULL;
    }
    if (node->data>x)
    {
        findpri(node->lson,x);
    }
    else if (node->data<x)
    {
        findpri(node->rson,x);
    }
    else return node;
}

template <class T>
treenode<T>*bst<T>::find_(T x)
{
    findpri(root,x);
}

template <class T>
void bst<T>::deletepri(treenode<T>*&node,T x)
{
   if (node==NULL)
        return;
   if (x<node->data)
   {
       deletepri(node->lson,x);
   }
   else if (x>node->data)
   {
       deletepri(node->rson,x);
   }
   else
   {
       if (node->lson&&node->rson)
       {
           treenode<T>*temp=node->rson;
           while(temp->lson!=NULL)
           {
               temp=temp->lson;
           }

       }
       else
       {
           treenode<T>*temp=node->rson;
           if (node->lson==NULL)
           {
               node=node->rson;
           }
           else if (node->rson==NULL)
           {
            node=node->lson;
           }
           delete (temp);

       }
   }
   return;
}

template <class T>
void bst<T>::delete_(T x)
{
    deletepri(root,x);
}

template <class T>
void bst<T>::insubtree(treenode<T>*node)
{
    if (node==NULL)return;
    insubtree(node->lson);
    std::cout<<node->data<<" ";
    insubtree(node->rson);
}

template <class T>
void bst<T>::traversal()
{
    insubtree(root);
}




#include <iostream>
#include "bst.cpp"
using namespace std;
int main()
{
  bst<int> a;
  a.insert_(22);
  a.insert_(34);
  a.insert_(1);
  a.insert_(12);
  a.delete_(34);
  a.traversal();

}

二叉tree