程序代码：

/*

 * Author: Devil Wang

 * Data: 01-21-2010

 * Notes: Template For Binary Tree

 */
#ifndef __BINTREE_H_
#define __BINTREE_H_
#include<iostream>
#include<cstdlib>
using std::cin;
using std::cout;
struct Exception{};
template<class KeyType,class InfoType>
     struct TNode
     {
      KeyType key;
      InfoType info;
      TNode<KeyType,InfoType> *left;
      TNode<KeyType,InfoType> *right;
      TNode<KeyType,InfoType> *parent;
      TNode<KeyType,InfoType>():left(NULL),right(NULL),parent(NULL){}
      TNode<KeyType,InfoType>(KeyType val, InfoType infoval=0):key(val),left(NULL),right(NULL),parent(NULL)
           {
            info=infoval;
           }
      friend ostream & operator<<(ostream &out,TNode<KeyType,InfoType> &Node)
           {
            out<<Node.key;
            return out;
           }
     } ;
template<class KeyType, class InfoType>
     class BinTree
{
private:
     TNode<KeyType,InfoType> *root;
     size_t Size;
protected:
     TNode<KeyType,InfoType> *minimum( TNode<KeyType,InfoType> *point)const
     {
      TNode<KeyType,InfoType> *p=point;
      while( NULL != p->left )
      {
           p=p->left;
      }
      try{
           if( NULL == p )
            throw Exception();
           return p;
      }catch( Exception e )
       {
        exit;
       }
     }
     TNode<KeyType,InfoType> * maximum(TNode<KeyType,InfoType> *point)const
     {
      TNode<KeyType,InfoType> *p=point;
      while( NULL != p->right )
      {
           p=p->right;
      }
      try{
           if( NULL == p )
            throw Exception();
           return p;
      }catch( Exception e )
       {
        exit;
       }

     }
     int leafcont(TNode<KeyType,InfoType> *pointer )
     {
      static int cont=0;
      if (NULL!=pointer)
      {
           leafcont(pointer->left);
           if(NULL== pointer->left && NULL==pointer->right)
           {
            cont++;
           }
           leafcont(pointer->right);
           return cont;
      }
     }
     void travel(TNode<KeyType,InfoType> *T)const
     {
      if( NULL!=T )
      {
           travel(T->left);
           cout<<*T<<" ";
           travel(T->right);
      }
      return ;
     }
public:
     BinTree<KeyType,InfoType>():root(NULL),Size(0){}
     BinTree<KeyType,InfoType>(int n):root(NULL),Size(0)
     {
      KeyType m;
      for(int i=0; i<n;i++)
      {
           cin>>m;
           BTinsert(m);
      }
     }
     ~BinTree()
     {
          TNode<KeyType,InfoType> *p;
          while( NULL != root->left || NULL != root->right)
          {
               p=minimum(root);
               BTDelete(p);
          }
     if( NULL !=root )
     {
          delete root;
     }
     }
     void BTInsert(KeyType val)
     {
      if( NULL == root)
      {
           root=new TNode<KeyType,InfoType>(val);
           root->parent=root;
           Size++;
           return ;
      }
      else
      {
           TNode<KeyType,InfoType> *pr=root,*cur;
           cur=(root->key>val)?root->left:root->right;
           while( NULL != cur )
           {
            pr=cur;
            cur=cur->key>val?cur->left:cur->right;
           }
           try{
            if( NULL != cur )
             throw Exception();
            cur=new TNode<KeyType,InfoType> (val);
            cur->parent=pr;
            if( pr->key > val)
             pr->left=cur;
            else
             pr->right=cur;
           }catch( Exception())
        {
             cout<<"Catch An Exception"<<endl;
             cout<<"BTInsert"<<endl;
             exit;
        }
           Size++;
      }
     }
     TNode<KeyType,InfoType> * BTSearch(KeyType val)const
     {
      TNode<KeyType,InfoType> * p=root;
      while( NULL != p && p->key!=val )
      {
           p=(p->key>val)?p->left:p->right;
      }
      try
      {
           if( NULL == p )
            throw Exception();
           return p;
      }catch ( Exception e)
       {
        cout<<"Catch An Exception"<<endl;
        cout<<"BTSearch"<<endl;
        return NULL;
       }
     }
     TNode<KeyType,InfoType> *BTMaximum()const{return maximum(root);}
     TNode<KeyType,InfoType> *BTMinimum()const{return minimum(root);}
     size_t size()
     {
      return Size;
     }
     bool empty()
     {
      return Size==0;
     }
     TNode<KeyType,InfoType> *BTSuccessor( TNode<KeyType,InfoType> *pointer )const
     {
      try
      {
           TNode<KeyType,InfoType> *point=pointer;
           if( NULL == point || point== maximum(root))
           {
            throw Exception();
           }
           if ( NULL != point->right )
            return point->right;
           TNode<KeyType,InfoType> *pr=point->parent;
           if( NULL == pr )
            throw Exception();
           while( NULL != pr && point==pr->right )
           {
            point=pr;
            pr=pr->parent;
           }
           return pr;
      }catch( Exception e)
       {
        cout<<"Catch An Exception" <<endl;
        cout<<"BTSuccessor"<<endl;
        return NULL;
       }
     }
     TNode<KeyType,InfoType> * BTPredecessor(TNode<KeyType,InfoType> *pointer )const
     {
      try
      {
           TNode<KeyType,InfoType> *point=pointer,*pr;
           if( NULL == point || point == BinTree::minimum(root))
            throw Exception();
           if( NULL != point->left )
            return point->left;
           pr=point->parent;
           while( pr->left == point && NULL != pr )
           {
            point=pr;
            pr=pr->parent;
           }
           return pr;
      }catch ( Exception e )
       {
        cout<<"Catch An Exception" <<endl;
        cout<<"BTPredecessor"<<endl;
        return NULL;
       }
     }
     void BTDelete( TNode<KeyType,InfoType> * z)
     {
      TNode<KeyType,InfoType> *x,*y;
      if ( NULL == z->left && NULL == z->right && z==z->parent )
      {
           delete z;
           z=NULL;
           root=NULL;
           Size--;
           return ;
      }
      if( NULL==z->left || NULL == z->right )
           y=z;
      else
           y=BinTree::BTSuccessor(z);
      if( NULL != y->left)
           x=y->left;
      else
           x=y->right;
      if ( NULL !=x )
           x->parent=y->parent;
      if( y->parent==y)
      {
           root=x;
           x->parent=x;
      }
      else if (y== y->parent->left)
           y->parent->left=x;
      else
           y->parent->right=x;
      if( z!=y )
      {
           z->key=y->key;
           z->info=y->info;
      }
      delete y;
      Size--;
     }
     void BTTravel()
     {
      travel(root);
      cout<<endl;
     }
     int BTLeafCont(){return leafcont(root);} 
};
#endif