BinaryTree

//
// Created by ZC on 2019-07-06.
//
#include<iostream>
#include<string>
using namespace std;
template<typename treeElemType>
class BinaryTree; // 前置声明


template <typename valType>
class BTnode{
public:
    BTnode(const valType&);
    void insert_value(const valType &val);
    void remove_value(const valType&, BTnode *&);
    static void lchild_leaf(BTnode *leaf, BTnode *subtree);
    void preorder(BTnode *, std::ostream &) const;
    void display_val(BTnode *,std::ostream &);
    friend class BinaryTree<valType>;
private:
    valType _val;
    int _cnt;
    BTnode *_lchild;
    BTnode *_rchild;
};


template <typename treeElemType>
class BinaryTree{
public:
    BinaryTree();
    BinaryTree(const BinaryTree& );
    ~BinaryTree();
    BinaryTree& operator=(const BinaryTree&);
    void insert(const treeElemType&);
    bool empty() {return _root == 0;}
    void remove(const treeElemType&);
    void remove_root();
    void clear(BTnode<treeElemType> *);
    void preorder(BTnode<treeElemType>*, ostream &);
    void display_val(BTnode<treeElemType>*, ostream &);
    BTnode<treeElemType> * return_root();
private:
    BTnode<treeElemType> *_root;
    void copy(BTnode<treeElemType>*tar, BTnode<treeElemType>*src);
};

template <typename treeElemType>
inline BTnode<treeElemType> * BinaryTree<treeElemType>::return_root() {
    return _root;
}

template <typename treeElemType>
inline void BinaryTree<treeElemType>::display_val(BTnode<treeElemType>*tar, ostream &os) {
    if (tar)
        os << tar->_val<< ' ';

}

template <typename treeElemType>
void BinaryTree<treeElemType>::preorder(BTnode<treeElemType>* tar, ostream &os)
{
    if (tar)
    {
        display_val(tar, os);
        if(tar->_lchild) preorder(tar->_lchild, os);
        if(tar->_rchild) preorder(tar->_rchild, os);
    }
}
template <typename treeElemType>
inline BinaryTree<treeElemType>::
BinaryTree() : _root(0)
{}

template <typename treeElemType>
inline BinaryTree<treeElemType>::
BinaryTree(const BinaryTree &rhs)
{copy(_root, rhs._root);}

template <typename treeElemType>
inline BinaryTree<treeElemType>::
        ~BinaryTree() {clear(this->_root);}

template <typename treeElemType>
inline BinaryTree<treeElemType>&
BinaryTree<treeElemType>::
operator=(const BinaryTree &rhs)
        {
            if(this != &rhs) // 取地址
            {clear(this->_root); copy(_root, rhs._root);}
            return *this;
        }

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

template <typename valType>
inline BTnode<valType>::
BTnode(const valType &val):_val(val) //成员函数初始化，因为val可能是类类型
{
    _cnt = 1;
    _lchild = _rchild = 0;
}


template <typename valType>
void 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>
void BTnode<valType>::
lchild_leaf(BTnode *leaf, BTnode *subtree) { //一直搜索到最左边叶节点
    while( subtree -> _lchild)
        subtree = subtree -> _lchild;
    subtree->_lchild = leaf;
}

// *& prev: reference to pointer
template <typename valType>
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;
                else BTnode<valType>::lchild_leaf(_lchild, prev->_lchild);
            }
        }else
            prev = _lchild;
        delete this;
    }
}

template <typename treeElemType>
inline void BinaryTree<treeElemType>::
remove(const treeElemType &elem) {
    if (_root)
    {
        if (_root->_val == elem)
            remove_root();
        else
            _root->remove_value(elem, _root);
    }
}

template<typename treeElemType>
inline void BinaryTree<treeElemType>::
remove_root() {
    if(!_root) return;

    BTnode<treeElemType> *tmp = _root;
    if(_root->_rchild)
    {
        _root = _root->_rchild;
        //搬动左子节点到右子节点的左子树底部
        if(tmp->_lchild)
        {
            BTnode<treeElemType> *lc = tmp->_lchild;
            BTnode<treeElemType> *newlc = _root->_lchild;
            if (!newlc)
                //没有任何子树
                _root->_lchild = lc;
            else BTnode<treeElemType>::lchild_leaf(lc, newlc);
        }

    }
    else _root = _root->_lchild;

    delete tmp;
}

template <typename treeElemType>
void BinaryTree<treeElemType>::
clear(BTnode<treeElemType> *pt)
{
    if (pt){
        clear(pt->_rchild);
        clear(pt->_lchild);
        delete pt;
    }
}


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>::display_val(BTnode *pt, std::ostream &os) {
    if (pt)
        os << pt->_val;
}

test:

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");

    cout << "Preorder travelsal : \n";
    bt.preorder(bt.return_root(), cout);

    bt.remove("Piglet");
    cout << "\nPreorder traversal after Piglet removal: \n";
    bt.preorder(bt.return_root(), cout);

    bt.remove("Eeyore");
    cout << "\nPreorder traversal after Eeyore removal: \n";
    bt.preorder(bt.return_root(), cout);
    return 0;
}


Preorder travelsal : 
Piglet Eeyore Chris Kanga Roo Pooh Tigger 
Preorder traversal after Piglet removal: 
Roo Pooh Eeyore Chris Kanga Tigger 
Preorder traversal after Eeyore removal: 
Roo Pooh Kanga Chris Tigger 
Process finished with exit code 0