程序代码：
-BASH-4.0.35$ cat BinTree.h
/*
* 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
