模板

//
#include
using namespace std;
#define T char

struct node
{
    T data;
    node *x,*y;
    node( T in=0,node *xx=NULL,node *yy=NULL ):data(in),x(xx),y(yy) {}
};

// new_node 中序遍历是递增序列
node* new_node( node *root,const T& data )  
{
    if( root==NULL ) 
    {
        root=new node( data ); return root;
    }
    if( data <= root->data )    
        root->x=( root->x,data );
    else                        
        root->y=( root->y,data );
    return root;
}

// find_node
node* find_node( node *root,const T& data )
{
    if( root==NULL ) return NULL;
    if( data==root->data ) return root;

    if( data < root->data )
        return find_node( root->x,data );
    else
        return find_node( root->y,data );
}
node* find_node( node *root,const T& data )
{
    node *now=root;
    while( now && data != now->data )
    {
        if( data < now->data ) 
            now=now->x;
        else
            now=now->y;
    }
    return now;
}

// insert_node
void insert_node( node *root,const T& data )
{
    if( root==NULL )
    {
        root=new node( data ); return ;
    }
    node *now=root;
    node *dad=NULL;
    bool is_x=true;

    while( now )
    {
        dad=now;
        if( data < now->data )  { now=now->x; is_x=1; }
        else                    { now=now->y; is_x=0; }
    }
    if( is_x )  dad->x=new node( data );
    else        dad->y=new node( data );
}