#ifndef BITREE_H
#define BITREE_H
template<typename elemtype> class bitnode
{
public:
bitnode();//构造函数
bitnode( const bitnode<elemtype>& );//拷贝构造函数
const elemtype date () const;//读取数据
const bitnode<elemtype> *lchild () const;//返回左指针
const bitnode<elemtype> *rchild () const;//返回右指针
void get_date( const elemtype );//输入数据
void get_lchild ( const bitnode<elemtype>* );//输入左指针
void get_rchild ( const bitnode<elemtype>* );//输入右指针
void operator =( const bitnode<elemtype>& );//赋值
private:
elemtype _date;//节点数据
bitnode<elemtype> *_lchild,*_rchild;//左右孩子指针
};//二叉树的节点
//bitnode类函数实现
template<typename elemtype>
bitnode<elemtype>::bitnode()
{
get_date( 0 );
get_rchild( 0 );
get_lchild( 0 );
}
template<typename elemtype >const
bitnode<elemtype>* bitnode<elemtype>::lchild() const
{
return _lchild;
}
template<typename elemtype> const
bitnode<elemtype>* bitnode<elemtype>::rchild() const
{
return _rchild;
}
template<typename elemtype> const
elemtype bitnode<elemtype>::date () const
{
return _date;
}
template<typename elemtype>
void bitnode<elemtype>::get_date( const elemtype de )
{
_date = de;
}
template<typename elemtype>
void bitnode<elemtype>::
get_lchild( const bitnode<elemtype> *pev)
{
_lchild = ( bitnode<elemtype>* ) pev;
}
template<typename elemtype>
void bitnode<elemtype>::
get_rchild ( const bitnode<elemtype> *pev)
{
_rchild = ( bitnode<elemtype>* ) pev;
}
//tree类
template<typename elemtype> class BiTree
{
public:
BiTree();//构造函数
BiTree( const BiTree<elemtype>& );
const bitnode<elemtype>* copy( const bitnode<elemtype>* );
void print() const;//打印树中数据
const bool empty() const;//测试树是否为空
const int node() const;//返回节点个数
void operator= ( const BiTree<elemtype>& );
private:
int node_nu;//节点个数
bitnode<elemtype> *pv;//根指针
void add_node();//增加节点
const bitnode<elemtype>* init();// 初始化
void fvisit( const bitnode<elemtype>* ) const;//先序遍历
void mvisit( const bitnode<elemtype>* ) const;//中序遍历
void hvisit( const bitnode<elemtype>* ) const;//后序遍历
};
//二叉树类代码实现
//公有函数集合
template<typename elemtype>
BiTree<elemtype>::BiTree()
{
pv = NULL;
node_nu = 0;
pv = ( bitnode<elemtype>* ) init();
}
template<typename elemtype> BiTree<elemtype>::
BiTree( const BiTree<elemtype>& tree )
{
if( tree.empty() )
pv = ( bitnode<elemtype>* ) copy( tree.pv );
}
template<typename elemtype>
void BiTree<elemtype>::print() const
{
cout << "请选择打印顺序：先序[x]？中序[z]？后序[h]？:";
char ch;
cin >> ch;
if ( empty() != 0 ){
switch ( ch )
{
case 'x': fvisit( pv ); break;
case 'z': mvisit( pv ); break;
case 'h': hvisit( pv ); break;
default:cerr << "错误操作。无法输出!" << endl;
}
}
else
cerr << "树为空" << endl;
}
template<typename elemtype> const
bool BiTree<elemtype>::empty() const
{
if( node_nu == 0 )
return false;
else
return true;
}
template<typename elemtype> const
int BiTree<elemtype>::node() const
{
return node_nu;
}
template<typename elemtype> const
bitnode<elemtype>* BiTree<elemtype>::
copy( const bitnode<elemtype>* ptr )
{
bitnode<elemtype> *pev;
if( ptr == 0 )
return 0;
if ( ptr->date() == 0 )
pev = 0;
else {
if ( !( pev = new bitnode<elemtype> ) )
return 0 ;
add_node();
pev->get_date( ptr->date() );
pev->get_lchild( copy( ptr->lchild() ) );
pev->get_rchild( copy( ptr->rchild() ) );
}
return pev;
}
template<typename elemtype>
void BiTree<elemtype>::
operator =( const BiTree<elemtype>& tree )
{
if( tree.empty() )
pv = copy( tree.pv );
}
//私有函数集合
template<typename elemtype> const
bitnode<elemtype>* BiTree<elemtype>::init()
{
bitnode<elemtype> *pev;
elemtype de;
cout << "请输入第"
<< node() + 1
<< "个数据：";
cin >> de;
if ( de == 0 )
pev = NULL;
else {
if ( !( pev = new bitnode<elemtype> ) )
return 0 ;
add_node();
pev->get_date( de );
pev->get_lchild( init() );
pev->get_rchild( init() );
}
return pev;
}
template<typename elemtype>
void BiTree<elemtype>::add_node()
{
++node_nu;
}
template<typename elemtype>
void BiTree<elemtype>::
fvisit( const bitnode<elemtype> *pev ) const
{
if ( pev != NULL )
cout << pev->date() << endl;
if ( pev->lchild() != NULL )
fvisit( pev->lchild() );
if ( pev->rchild() != NULL )
fvisit( pev->rchild() );
}
template<typename elemtype>
void BiTree<elemtype>::
mvisit( const bitnode<elemtype> *pev ) const
{
if ( pev->lchild() != NULL )
mvisit( pev->lchild() );
if ( pev != NULL )
cout << pev->date() << endl;
if ( pev->rchild() != NULL )
mvisit( pev->rchild() );
}
template<typename elemtype>
void BiTree<elemtype>::
hvisit( const bitnode<elemtype> *pev ) const
{
if ( pev->lchild() != NULL )
hvisit( pev->lchild() );
if ( pev->rchild() != NULL )
hvisit( pev->rchild() );
if ( pev != NULL )
cout << pev->date() << endl;
}
#endif
