//////////////////////////////////////////////////
//oneDegree()私有成员函数
//递归统计子树subTree中度为1的结点的个数
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::oneDegree(BinTreeNode<T>* subTree)
{
    //子树不空
    if(subTree!=NULL)
    {
        //如果左右子树都不空
        if(subTree->leftChild!=NULL
            && subTree->rightChild!=NULL)
            //递归统计左右子树,并返回两者的和
            return oneDegree(subTree->leftChild)
            +oneDegree(subTree->rightChild);
        //如果左不空右空,则递归统计左子树,再加上当前结点
        else if(subTree->leftChild!=NULL
            && subTree->rightChild==NULL)
            return oneDegree(subTree->leftChild)+1;
        //如果左空右不空,则递归统计右子树,在加上当前结点
        else if(subTree->leftChild==NULL
            && subTree->rightChild!=NULL)
            return oneDegree(subTree->rightChild)+1;
        //左右子树都是空的说明是叶子结点,返回0
        else
            return 0;
    }
    //空则返回0
    else
        return 0;
};
///////////////////////////////oneDegree()函数结束

//////////////////////////////////////////////////
//twodegree()私有成员函数
//递归统计子树subTree中度为2的结点的个数
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::twoDegree(BinTreeNode<T>* subTree)
{
    //子树不空
    if(subTree!=NULL)
    {
        //如果左右子树都不空
        if(subTree->leftChild!=NULL
            && subTree->rightChild!=NULL)
            //递归统计左右子树,并返回两者的和,并加1
            return 1+twoDegree(subTree->leftChild)
            +twoDegree(subTree->rightChild);
        //如果左空右不空,则递归统计右子树
        else if(subTree->leftChild==NULL
            && subTree->rightChild!=NULL)
            return twoDegree(subTree->rightChild);
        //如果左不空右空,则递归统计左子树
        else if(subTree->leftChild!=NULL
            && subTree->rightChild==NULL)
            return twoDegree(subTree->leftChild);
        //叶子结点
        else
            return 0;
    }
    else
        return 0;
};
///////////////////////////////twoDegree()函数结束

//////////////////////////////////////////////////
//zeroDegree()私有成员函数
//递归统计子树subTree中度为0的结点的个数
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::zeroDegree(BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        //如果左右子树都不空
        if(subTree->leftChild==NULL
            && subTree->rightChild==NULL)
            //递归统计左右子树,并返回两者的和,并加1
            return 1;
        //如果左空右不空,则递归统计右子树
        else if(subTree->leftChild==NULL
            && subTree->rightChild!=NULL)
            return zeroDegree(subTree->rightChild);
        //如果左不空右空,则递归统计左子树
        else if(subTree->leftChild!=NULL
            && subTree->rightChild==NULL)
            return zeroDegree(subTree->leftChild);
        //叶子结点
        else
            return zeroDegree(subTree->rightChild)
            +zeroDegree(subTree->rightChild);
    }
    else
        return 0;
};
//////////////////////////////zeroDegree()函数结束

//////////////////////////////////////////////////
//Depth()私有成员
//计算指定结点p在子树subTree中的深度
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::Depth(BinTreeNode<T>* p
            ,BinTreeNode<T>* subTree)
{
    //如果子树不空
    if(subTree!=NULL)
    {
        //如果就是根结点则深度为1
        if(p==subTree)
            return 1;
        else
        {
            //递归求p在左子树里的深度
            int ld=Depth(p,subTree->leftChild);
            //递归求p在右子树里的深度
            int rd=Depth(p,subTree->rightChild);
            if(ld!=0)
                //左子树深度加1
                return 1+ld;
            else if(rd!=0)
                //右子树深度加1
                return 1+rd;
            else
                //没有找到则返回0
                return 0;
        }
    }
    else
        //空则深度为0
        return 0;
};
///////////////////////////////////Depth()函数结束

//////////////////////////////////////////////////
//私有成员函数deleteLeaf()
//删除子树subTree里的所有的叶子结点
//本算法是寻找叶子结点的父结点
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::deleteLeaf(BinTreeNode<T>* subTree)
{
    //如果子树不空
    if(subTree!=NULL)
    {
        //如果当前结点就是叶子结点
        if(subTree->leftChild==NULL
            && subTree->rightChild==NULL)
            return;
        else
        {
            //如果左子结点是叶子结点
            if(subTree->leftChild->leftChild==NULL
                && subTree->leftChild->rightChild==NULL)
                //删除该左子结点
                subTree->leftChild=NULL;
            else
                //递归删除左子树的叶子
                deleteLeaf(subTree->leftChild);
            
            //如果右子结点是叶子结点
            if(subTree->rightChild->leftChild==NULL
                && subTree->rightChild->rightChild==NULL)
                //删除该右子结点
                subTree->rightChild=NULL;
            else
                //递归删除右子树的叶子
                deleteLeaf(subTree->rightChild);
        }
    };
};
//////////////////////////////deleteLeaf()函数结束

//////////////////////////////////////////////////
//maxVal()私有成员函数
//递归找出子树subTree中结点的最大值
//////////////////////////////////////////////////
template<class T>
T BinaryTree<T>::maxVal(BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        T maxl,maxr;

        //求出左子树的最大值
        maxl=maxVal(subTree->leftChild);
        //求出右子树的最大值
        maxr=maxVal(subTree->rightChild);

        //返回根结点，左子结点,右子结点中最大的那个
        if(subTree->data>maxl && subTree->data>maxr)
            return subTree->data;
        else if(maxl>subTree->data && maxl>maxr)
            return maxl;
        else
            return maxr;
    }
    else
        return 0;
};
//////////////////////////////////maxVal()函数结束

//////////////////////////////////////////////////
//maxVal()私有成员函数
//递归找出子树subTree中结点的最大值
//////////////////////////////////////////////////
template<class T>
T BinaryTree<T>::maxVal(BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        T maxl,maxr;

        //求出左子树的最大值
        maxl=maxVal(subTree->leftChild);
        //求出右子树的最大值
        maxr=maxVal(subTree->rightChild);

        //返回根结点，左子结点,右子结点中最大的那个
        if(subTree->data>maxl && subTree->data>maxr)
            return subTree->data;
        else if(maxl>subTree->data && maxl>maxr)
            return maxl;
        else
            return maxr;
    }
    else
        return 0;
};
//////////////////////////////////maxVal()函数结束

//////////////////////////////////////////////////
//DoubleOrder()私有成员函数
//双序遍历一棵二叉树,即先访问子树根结点,
//再双序访问左子树,再次访问子树根结点,
//最后在双序访问右子树
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::DoubleOrder(BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        //先访问根结点
        cout<<subTree->data;
        //访问左子树
        DoubleOrder(subTree->leftChild);
        //再访问根结点
        cout<<subTree->data;
        //最后访问右子树
        DoubleOrder(subTree->rightChild);
    };
};
/////////////////////////////DoubleOrder()函数结束

//////////////////////////////////////////////////
//PrintDepth()保护成员函数
//以前序的方式显示每个结点,并显示它的深度
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::PrintDepth(BinTreeNode<T>* subTree
                ,int depth)
{
    if(subTree!=NULL)
    {
        //访问根结点
        cout<<subTree->data<<":"<<depth<<"  ";
        //递归访问左右子树
        PrintDepth(subTree->leftChild,depth+1);
        PrintDepth(subTree->rightChild,depth+1);
    };
};
//////////////////////////////PrintDepth()函数结束

//////////////////////////////////////////////////
//SearchpreOrder()私有成员函数
//得到中序序列中第k个结点的指针
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::SearchpreOrder(int k
            ,BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        int T=Size(subTree);             //树的总结点数
        int TL=Size(subTree->leftChild); //树的左子树结点数
        int TR=Size(subTree->rightChild);//树的右子树结点数

        if(k==1)                  //如果k=1,那要找的就是子树根结点
             return subTree;
        else if((k-1)<=TL)        //如果在左子树中
            return SearchpreOrder(k-1
            ,subTree->leftChild);
        else if((k-1)>TL && k<=T) //如果在右子树中
            return SearchpreOrder(k-1-TL
            ,subTree->rightChild);
        else                      //如果超过树的总结点数
            return NULL;
    }
    else
        return NULL;
};
/////////////////////////私有SearchOrder()函数结束