//////////////////////////////////////////////////
//CreateBinaryTree()私有成员函数
//用输描述字符流递归递归创建一个二叉树
//输入的字符流必须是前序序列的二叉树
//每个叶子结点后都要加上两个#的结束符号结点
//////////////////////////////////////////////////
template<class T>
void CreateBinaryTree(istream& in
            ,BinTreeNode<T>* subTree)
{
    T item;
    //递归建立二叉树
    if(!in.eof())
    {
        in>>item;               //输入字符
        if(item!=RefValue)      //如果没有到结束符号
        {
            subTree=new BinTreeNode<T>(item);
                                //新建子树的根结点
            if(subTree==NULL)
            {cout<<"根结点内存分配失败!"<<endl;exit(1);}
            
            CreateBinaryTree(in,subTree->leftChild);
                                //递归建立左子树
            CreateBinaryTree(in,subTree->rightChild);
                                //递归建立右子树
        }
        else
            return NULL;
    }
};
////////////////////////CreateBinaryTree()函数结束

//////////////////////////////////////////////////
//私有成员函数Destroy() 释放二叉树的存储空间
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::Destroy(BinTreeNode<T>*& subTree)
{
    if(subTree!=NULL)
    {
        //递归释放左子树
        Destroy(subTree->leftChild);
        //递归释放右子树
        Destroy(subTree->rightChild);
        //释放当前结点的空间
        delete subTree;
    };
};
/////////////////////////////////Destroy()函数结束

//////////////////////////////////////////////////
//Exist()私有成员函数
//在指定的子树中查找元素x是否存在
//////////////////////////////////////////////////
template<class T>
bool BinaryTree<T>::Exist(BinTreeNode<T>* subTree
                ,const T& x)
{
    //若子树不空
    if(subTree!=NULL)
    {
        //如果结点元素相等
        if(subTree->data==x)
            return true;
        else
            //递归比较左右子树
            return Exist(subTree->leftChild,x)
            ||Exist(subTree->rightChild,x);
    }
    else
        return false;
};
///////////////////////////////////Exist()函数结束

//////////////////////////////////////////////////
//私有成员函数Copy()   二叉树的复制
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::Copy(
            BinTreeNode<T>* orignode)
{
    if(orignode!=NULL)
    {
        //依据orignode的内容,新建一个结点
        BinTreeNode<char>* p=new
            BinTreeNode<char>(orignode->data);
        //递归复制orignode的左子树
        p->leftChild=Copy(orignode->leftChild);
        //递归复制orignode的右子树
        p->rightChild=Copy(orignode->rightChild);
        return p;
    }
    else
        return NULL;
};
////////////////////////////////////Copy()函数结束

//////////////////////////////////////////////////
//Height()私有成员函数
//返回树subTree的高度
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::Height(BinTreeNode<T>* subTree)
{
    //如果树为空则返回0
    if(subTree==NULL)
        return 0;
    else
    {
        //左子树深度
        int p1=Height(subTree->leftChild);
        // 右子树深度
        int p2=Height(subTree->rightChild);
        if(p1>=p2)
            return 1+p1;
        else
            return 1+p2;
    };
};
//////////////////////////////////Height()函数结束

//////////////////////////////////////////////////
//私有成员函数Size()
//得到二叉树的总接点的个数
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::Size(BinTreeNode<T>* subTree)
{
    //子树为空,则结点数为0
    if(subTree==NULL)
        return 0;
    else
        return 1+Size(subTree->leftChild)
        +Size(subTree->rightChild);
};
////////////////////////////////////Size()函数结束

//////////////////////////////////////////////////
//Parent()私有成员函数
//返回树subTree中,current结点的父结点
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::Parent(
                     BinTreeNode<T>* subTree
                    ,BinTreeNode<T>* current)
{
    if(subTree!=NULL)
    {
        //如果subTree就是current的父结点
        if(subTree->leftChild==current
            || subTree->rightChild==current)
            return subTree;
        else
        {
            BinTreeNode<T> *pl,*pr;
            //递归搜索左子树
            pl=Parent(subTree->leftChild,current);
            //递归搜索右子树
            pr=Parent(subTree->rightChild,current);
            //只要其中一个不空就返回
            if(pl!=NULL)
                return pl;
            else if(pr!=NULL)
                return pr;
            else
                return NULL;
        }
    }
    else
        return NULL;
};
//////////////////////////////////Parent()函数结束

//////////////////////////////////////////////////
//Find()私有成员函数
//在子树subTree中搜索值为x的结点的指针
//如果不存在该结点就返回NULL
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::Find(
            BinTreeNode<T>* subTree
                    ,const T& x)const
{
    if(subTree!=NULL)
    {
        //如果subTree里的内容就是x
        if(subTree->data==x)
            return subTree;
        //如果不是
        else
        {
            BinTreeNode<T>* pl=
                Find(subTree->leftChild,x);
            BinTreeNode<T>* pr=
                Find(subTree->rightChild,x);
            //递归搜索左右子树
            if(pl!=NULL)
                return pl;
            else if(pr!=NULL)
                return pr;
            //左右子树中都没有x结点就返回NULL
            else
                return NULL;
        }
    }
    else
        return NULL;
};
////////////////////////////////////Find()函数结束

//////////////////////////////////////////////////
//私有成员函数Traverse()
//搜索并前序遍历输出
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::Traverse(BinTreeNode<T>* subTree
                ,ostream& out)
{
    if(subTree!=NULL)
    {
        //显示结点信息
        out<<subTree->data<<" ";
        //递归遍历左右子树
        Traverse(subTree->leftChild,out);
        Traverse(subTree->rightChild,out);
    }
};
////////////////////////////////Traverse()函数结束

//////////////////////////////////////////////////
//友元重载>>输入运算符输入二叉树
//////////////////////////////////////////////////
template<class T>
istream& operator>>(istream& in,BinaryTree<T>& Tree)
{
    //输入儿茶树的描述字符串
    char s[50];
    in>>s;
    BinTreeNode<T>* r;
    Tree.CreateBinTree(s,r);
    Tree.root=r;
    return in;
};
///////////////////////////////////////友元重载结束

///////////////////////////////////////////////////
//友元重载<<输出运算符输出二叉树
///////////////////////////////////////////////////
template<class T>
ostream& operator<<(ostream& out,BinaryTree<T>& Tree)
{
    Tree.Traverse(Tree.root,out);
    return out;
};
///////////////////////////////////////友元重载结束