-
멤버 템플릿 함수도 정의할 수 있다.
#ifdef _MSC_VER
#pragma warning( disable: 4786 )
#endif
#include <iostream>
#include <vector>
using namespace std;
template <typename elemType>
class BinaryTree;
template <typename elemType>
class BTnode;
template <typename valType>
ostream&
foo( ostream &os, const BTnode<valType> &bt );
template <typename valType>
class BTnode {
friend class BinaryTree<valType>;
friend ostream&
// foo<valType>( ostream&, const BTnode<valType>& );
foo( ostream&, const BTnode<valType>& );
public:
BTnode( const valType &val );
const valType& value() const { return _val; }
int occurs() const{ return _cnt; }
void remove_value( const valType&, BTnode*& );
void insert_value( const valType& );
bool find_value( const valType& ) const;
void preorder ( BTnode*, ostream& ) const;
void inorder ( BTnode*, ostream& ) const;
void postorder( BTnode*, ostream& ) const;
static void lchild_leaf( BTnode *leaf, BTnode *subtree );
private:
int _cnt; // occurrence count
valType _val;
BTnode *_lchild;
BTnode *_rchild;
void display_val( BTnode *pt, ostream &os ) const;
BTnode( const BTnode& );
BTnode& operator=( const BTnode& );
};
template <typename valType>
inline
BTnode<valType>::
BTnode( const valType &val )
: _val( val )
{
_cnt = 1;
_lchild = _rchild = 0;
}
template <typename valType>
void
BTnode<valType>::
insert_value( const valType &val )
{
if ( val == _val )
{
_cnt++;
(*BinaryTree<valType>::os()) << "BTnode::insert_value: increment count( "
<< val << " : " << _cnt << " )\n";
return;
}
if ( val < _val ){
if ( ! _lchild ){
_lchild = new BTnode( val );
(*BinaryTree<valType>::os()) << "ok: BTnode::insert_value at left child( " << val << " )\n";
}
else _lchild->insert_value( val );
}
else {
if ( ! _rchild ){
_rchild = new BTnode( val );
(*BinaryTree<valType>::os()) << "ok: BTnode::insert_value at right child( " << val << " )\n";
}
else _rchild->insert_value( val );
}
}
template <typename valType>
bool
BTnode<valType>::
find_value( const valType &val ) const
{
if ( val == _val )
return true;
if ( val < _val ){
if ( ! _lchild )
return false;
else return _lchild->find_value( val );
}
else {
if ( ! _rchild )
return false;
else return _rchild->find_value( val );
}
}
template <typename valType>
void
BTnode<valType>::
lchild_leaf( BTnode *leaf, BTnode *subtree )
{
while ( subtree->_lchild )
subtree = subtree->_lchild;
subtree->_lchild = leaf;
}
template <typename valType>
void
BTnode<valType>::
remove_value( const valType &val, BTnode *&prev )
{
if ( val < _val )
{
if ( ! _lchild )
return; // not present
else _lchild->remove_value( val, _lchild );
}
else
if ( val > _val )
{
if ( ! _rchild )
return; // not present
else _rchild->remove_value( val, _rchild );
}
else
{ // ok: found it
// reset the tree then delete this node
if ( _rchild )
{
prev = _rchild;
if ( _lchild )
if ( ! prev->_lchild )
prev->_lchild = _lchild;
else BTnode<valType>::lchild_leaf( _lchild, prev->_lchild );
}
else prev = _lchild;
delete this;
}
}
template <typename valType>
inline void BTnode<valType>::
display_val( BTnode *pt, ostream &os ) const
{
os << pt->_val;
if ( pt->_cnt > 1 )
os << "( " << pt->_cnt << " ) ";
else os << ' ';
}
template <typename valType>
void BTnode<valType>::
preorder( BTnode *pt, ostream &os ) const
{
if ( pt )
{
display_val( pt, os );
if ( pt->_lchild ) preorder( pt->_lchild, os );
if ( pt->_rchild ) preorder( pt->_rchild, os );
}
}
template <typename valType>
void BTnode<valType>::
inorder( BTnode *pt, ostream &os ) const
{
if ( pt )
{
if ( pt->_lchild ) inorder( pt->_lchild, os );
display_val( pt, os );
if ( pt->_rchild ) inorder( pt->_rchild, os );
}
}
template <typename valType>
void BTnode<valType>::
postorder( BTnode *pt, ostream &os ) const
{
if ( pt )
{
if ( pt->_lchild ) postorder( pt->_lchild, os );
if ( pt->_rchild ) postorder( pt->_rchild, os );
display_val( pt, os );
}
}
template <typename elemType>
class BinaryTree {
public:
BinaryTree();
BinaryTree( const vector< elemType >& );
BinaryTree( const BinaryTree& );
~BinaryTree();
BinaryTree& operator=( const BinaryTree& );
void insert( const vector< elemType >& );
void insert( const elemType& );
void remove( const elemType& );
void clear(){ clear( _root ); _root = 0; } // remove entire tree ...
bool empty() { return _root == 0; }
void inorder( ostream &os = *_current_os ) const { _root->inorder( _root, os ); }
void postorder( ostream &os = *_current_os ) const { _root->postorder( _root, os ); }
void preorder( ostream &os = *_current_os ) const { _root->preorder( _root, os ); }
bool find( const elemType& ) const;
ostream& print( ostream &os = *_current_os,
void (BinaryTree<elemType>::*traversal)( ostream& ) const =
&BinaryTree<elemType>::inorder ) const;
static void current_os( ostream *os ){ if ( os ) _current_os = os; }
static ostream* os() { return _current_os; }
private:
BTnode<elemType> *_root;
static ostream *_current_os;
// copy a subtree addressed by src to tar
void copy( BTnode<elemType>*&tar, BTnode<elemType>*src );
void clear( BTnode<elemType>* );
void remove_root();
};
template <typename elemType>
ostream *BinaryTree<elemType>::_current_os = &cout;
template <typename elemType>
inline
BinaryTree<elemType>::
BinaryTree()
: _root( 0 ){}
template <typename elemType>
inline
BinaryTree<elemType>::
BinaryTree( const BinaryTree &rhs )
{ copy( _root, rhs._root ); }
template <typename elemType>
inline
BinaryTree<elemType>::
~BinaryTree(){ clear(); }
template <typename elemType>
inline BinaryTree<elemType>&
BinaryTree<elemType>::
operator=( const BinaryTree &rhs )
{
if ( this != &rhs )
{
clear();
copy( _root, rhs._root );
}
}
template <typename elemType>
inline void
BinaryTree<elemType>::
insert( const elemType &elem )
{
if ( ! _root ){
(*BinaryTree<elemType>::os()) << "BinaryTree::insert: root( " << elem << " )\n";
_root = new BTnode<elemType>( elem );
}
else _root->insert_value( elem );
}
template <typename elemType>
BinaryTree<elemType>::
BinaryTree( const vector< elemType > &vec )
{
_root = 0;
for ( int ix = 0; ix < vec.size(); ++ix )
insert( vec[ ix ] );
}
template <typename elemType>
void
BinaryTree<elemType>::
insert( const vector< elemType > &vec )
{
for ( int ix = 0; ix < vec.size(); ++ix )
insert( vec[ ix ] );
}
template <typename elemType>
inline void
BinaryTree<elemType>::
remove( const elemType &elem )
{
if ( _root )
{
if ( _root->_val == elem )
remove_root();
else _root->remove_value( elem, _root );
}
}
template <typename elemType>
void
BinaryTree<elemType>::
remove_root()
{
if ( ! _root ) return;
BTnode<elemType> *tmp = _root;
if ( _root->_rchild )
{
_root = _root->_rchild;
BTnode<elemType> *lc = tmp->_lchild;
BTnode<elemType> *newlc = _root->_lchild;
// if left child of root is non-null
// attach it as leaf to left subtree
if ( lc )
if ( ! newlc )
_root->_lchild = lc;
else BTnode<elemType>::lchild_leaf( lc, newlc );
}
else _root = _root->_lchild;
delete tmp;
}
template <typename elemType>
void
BinaryTree<elemType>::
clear( BTnode<elemType> *pt )
{
if ( pt ){
clear( pt->_lchild );
clear( pt->_rchild );
delete pt;
}
}
template <typename elemType>
ostream&
BinaryTree<elemType>::
print( ostream &os,
void (BinaryTree::*traversal)( ostream& ) const ) const
{
(this->*traversal)( os );
return os;
}
// 함수 템플릿의 출력 연산자
template <typename elemType>
inline ostream&
operator<<( ostream &os, const BinaryTree<elemType> &bt )
{
os << "Tree: " << endl;
bt.print( os, &BinaryTree<elemType>::inorder );
return os;
}
template <typename elemType>
inline bool
BinaryTree<elemType>::
find( const elemType &elem ) const
{
return ! _root
? false
: _root->find_value( elem );
}
template <typename elemType>
void
BinaryTree<elemType>::
copy( BTnode<elemType> *&tar, BTnode<elemType> *src )
{
if ( src ) {
tar = new BTnode<elemType>( src->_val );
if ( src->_lchild ) copy( tar->_lchild, src->_lchild );
if ( src->_rchild ) copy( tar->_rchild, src->_rchild );
}
}
참조 사이트: