#include<iostream>
using namespace std;

template <typename elemType>
class BinaryTree;

template <typename elemType>
class BTnode;

template <typename valType>
class BTnode{
    friend class BinaryTree<valType>;
public:
    BTnode(const valType &);

    void insert_value(const valType &);
    // void lchild_leaf(BTnode *leaf,BTnode *subtree);
    void remove_value(const valType &,BTnode *&);

    void preorder(BTnode *pt,ostream &os) const;
    void inorder(BTnode *pt,ostream &os) const;
    void postorder(BTnode *pt,ostream &os) const;

    static void lchild_leaf(BTnode *leaf,BTnode *subtree);
private:
    valType _val;
    int _cnt;
    BTnode *_lchild;
    BTnode *_rchild;

    void display_val( BTnode *pt, ostream &os ) const;
};

template<typename valType>
inline BTnode<valType>::
BTnode(const valType &val)
    : _val(val)
{ 
    _cnt = 1;
    _lchild = _rchild = 0;
}

template <typename valType>
void inline BTnode<valType>::
insert_value(const valType &val)
{
    if(val == _val)
    {
        _cnt++;
        return;
    }
    if(val < _val)
    {
        if(! _lchild)
            _lchild = new BTnode(val);
        else
            _lchild -> insert_value(val);
    }
    if(val > _val)
    {
        if(! _rchild)
            _rchild = new BTnode(val);
        else
            _rchild -> insert_value(val);
    }
}


template<typename valType>
inline void BTnode<valType>::
remove_value(const valType &val,BTnode *& prev)
{
    if(val < _val)
    {
        if(! _lchild)
            return;
        else
            _lchild -> remove_value(val,_lchild);
    }
    else if(val > _val)
    {
        if(!_rchild)
            return;
        else
            _rchild -> remove_value(val,_rchild);
    }
    else
    {
        if(_rchild)
        {
            prev = _rchild;
            if( _lchild)
                if(! prev -> _lchild)
                    prev -> _lchild = _lchild;//改变pointer指向的对象
                else
                    BTnode<valType>::lchild_leaf(_lchild,prev->_lchild);
        }
        else
            prev = _lchild;// 改变pointer本身
        delete this;
    }
}

template<typename valType>
inline void BTnode<valType>::
lchild_leaf(BTnode *leaf,BTnode *subtree)
{
    while(subtree->_lchild)
        subtree = subtree->_lchild;
    subtree->_lchild = leaf;
}

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{
    friend ostream& operator<< (ostream& os,const BinaryTree<elemType> &bt);
public:
    BinaryTree();
    BinaryTree(const BinaryTree &);
    ~BinaryTree();
    BinaryTree& operator=(const BinaryTree&);


    void clear(){if(_root){clear(_root);_root = 0;}}
    void insert(const elemType &);
    void remove(const elemType &);
    
    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 ); }

	void inorder()   const { _root->inorder( _root, cout ); }
    void postorder() const { _root->postorder( _root, cout ); }
    void preorder()  const { _root->preorder( _root, cout ); }
    // ostream& print( ostream &os = *_current_os,
    //                 void (BinaryTree<elemType>::*traversal)( ostream& ) const =
    //                       &BinaryTree<elemType>::inorder ) const;
    ostream& print( ostream &os);
private:
    // BTnode必须以template parameter list加以限定
    BTnode<elemType> *_root;
    // static ostream   *_current_os; 

    // 将src所指子树复制到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);
        }
    return *this;
}

template <typename elemType>
inline void
BinaryTree<elemType>::
insert(const elemType &elem)
{
    if(! _root)
        _root = new BTnode<elemType> (elem);
    else
        _root -> insert_value(elem);
}

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>
inline void BinaryTree<elemType>::
remove_root()
{
    if(! _root) return;
    BTnode <elemType> *tmp = _root;
    if(_root->_rchild)
    {
        _root = _root -> _rchild;
        if(tmp -> _lchild)
        {
            BTnode<elemType> *lc = tmp -> _lchild;
            BTnode<elemType> *newlc = _root -> _lchild;
            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>
ostream& 
BinaryTree<elemType>::
print( ostream &os)
{
	this->inorder();
	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;
// }

// friend ostream& operator<< (ostream& os,const BinaryTree<elemType> &bt);
template<typename elemType>
inline ostream&
operator<< (ostream& os,BinaryTree<elemType> &bt)
{
    os<<"Tree: "<<endl;
    bt.print(os);
    return os;
}


   
// 错误写法：
// template <typename elemType>
// inline BinaryTree<elemType>::
// BinaryTree& operator=(const BinaryTree &rhs)
// {
//     if(this != &rhs){
//         clear();
//         copy(_root,rhs._root);
//         }
//     return *this;
// }

int main(){
	BinaryTree<string> bt;
    bt.insert( "Piglet" );
    bt.insert( "Eeyore" );
	bt.insert( "Roo" );

	bt.insert( "Tigger" );
	bt.insert( "Chris" );
	bt.insert( "Pooh" );
	bt.insert( "Kanga" );
	bt.preorder();
    cout<<'\n';
    bt.remove("Piglet");
    bt.preorder();
    cout<<'\n';
	cout<<bt;
    return 0;
}