///////////////////////////////////////////////////
//友元函数Equal()
//比较以a,b为根结点的二叉树是否相等
///////////////////////////////////////////////////
template<class T>
bool Equal(BinTreeNode<T>* a,BinTreeNode<T>* b)
{
    //先比较子树的根结点
    if(a==NULL && b==NULL)
        return true;
    //根结点相等而且左右子树递归相等
    else if(a!=NULL && b!=NULL && a->data==b->data
            && Equal(a->leftChild,b->leftChild)
            && Equal(a->rightChild,b->rightChild))
    {
            return true;
    }
    else
        //不相等就返回false
        return false;
};
///////////////////////////友元函数Equanl()函数结束

///////////////////////////////////////////////////
//友元函数BinTreeEqual()
//比较两个二叉树是否相等
///////////////////////////////////////////////////
template<class T>
bool BinTreeEqual(BinaryTree<T>& BT1,BinaryTree<T>& BT2)
{
    //调用Equal(BinTreeNode<T>* a,BinTreeNode<T>* b)
    //递归函数
    return Equal(BT1.root,BT2.root);
};
////////////////////////////友元函数Equal()函数结束

///////////////////////////////////////////////////
//CreateByprein()公有成员函数
//通过二叉树的前序序列和中序序列建立一棵二叉树
///////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::CreateByprein(T* pre,T* in,int n)
{
    root=CreateByprein1(pre,in,n);
};
////////////////////////////CreateByprein()函数结束

///////////////////////////////////////////////////
//私有成员函数CreateByprein()
//通过前序序列和中序序列建立一棵二叉树
//输入的前序和中序序列必须一'#'结束
//pre是前序序列,in是中序序列,n为二叉树结点个数
///////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::CreateByprein1(T* pre
                        ,T* in,int n)
{
    //创建的子树的根结点指针
    BinTreeNode<T>* p;

    //递归结束的条件
    if(n==0)
        //如果二叉树长度为0,返回空
        return NULL;

    T s=pre[0];             //在前序中的第一个元素就是根结点
    p=new BinTreeNode<T>(s);//根据取出的根结点元素创建根结点

    //在根据前序得到的根结点拆分中序序列的过程
    for(int m=0;m<n;m++)    //在中序的序列中查找根结点的位置
    {
        if(in[m]==s)        //m就是根结点在中序中的位置
            break;
    };

    //得到左子树的前序和中序
    T* lp=new T[m];             //得到左子树的前序
    for(int i=0;i<m;i++)
        lp[i]=pre[i+1];

    T* li=new T[m];             //得到左子树的中序
    for(i=0;i<m;i++)
        li[i]=in[i];

    T* rp=new T[n-m+1];         //得到右子树的前序
    for(i=0;i<n-m+1;i++)
        rp[i]=pre[i+m+1];

    T* ri=new T[n-m+1];         //得到右子树的中序
    for(i=0;i<n-m+1;i++)
        ri[i]=in[i+m+1];

    //递归创建左子树
    p->leftChild=CreateByprein1(lp,li,m);
    //递归创建右子树
    p->rightChild=CreateByprein1(rp,ri,n-m-1);

    //释放内存空间
    delete lp;
    delete li;
    delete rp;
    delete ri;
    //返回当前根结点的指针
    return p;
};
////////////////////////////CreateByprein()函数结束

///////////////////////////////////////////////////
//友元重载==运算符
///////////////////////////////////////////////////
template<class T>    
bool operator==(BinaryTree<T>& BT1
                ,BinaryTree<T>& BT2)
{
    //判断两个二叉树是否相等
    return BinTreeEqual(BT1,BT2);
};
///////////////////////////////////////友元重载结束

//////////////////////////////////////////////////
//私有成员函数PrintBinaryTree()函数
//递归显示二叉树的广义表形式
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::PrintBinaryTree(
                BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        //显示根结点的内容
        cout<<subTree->data;
        //如果不是叶子结点就递归显示子树的内容
        if(subTree->leftChild!=NULL
            || subTree->rightChild!=NULL)
        {
            //显示左括号
            cout<<"(";
            //递归显示左子树
            PrintBinaryTree(subTree->leftChild);
            //显示,
            cout<<",";
            //递归显示右子树
            PrintBinaryTree(subTree->rightChild);
            //显示右括号
            cout<<")";
        }
    };
};
/////////////////////私有PrintBinaryTree()函数结束

//////////////////////////////////////////////////
//私有成员函数CountNode()函数
//递归统计以subTree为根的子树的所有的结点的个数
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::CountNode(BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
        //返回左右子树结点数之和并加1
        return 1+CountNode(subTree->leftChild)
            +CountNode(subTree->rightChild);
    else
        //如果为空则结点数为0
        return 0;
};
///////////////////////////////CountNode()函数结束

//////////////////////////////////////////////////
//GetNode()私有成员函数
//把二叉树当前的所有的结点按层次顺序放入一个数组
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::GetNode(BinTreeNode<T>** w)
{
    //数组下标的计数器
    int i=0;
    //层次遍原始历用的队列
    LinkedQueue<BinTreeNode<T>* > Q;
    //指针
    BinTreeNode<T>* p=root;
    //先把根结点入栈
    Q.EnQueue(p);
    //层次遍历
    while(!Q.IsEmpty())
    {
        //先从队列中读取一个元素
        Q.DeQueue(p);
        //把该结点送入数组
        w[i]=p;i++;
        //把左子结点入队列
        if(p->leftChild!=NULL)
            Q.EnQueue(p->leftChild);
        //把右子结点入队列
        if(p->rightChild!=NULL)
            Q.EnQueue(p->rightChild);
    };
};
/////////////////////////////////GetNode()函数结束

//////////////////////////////////////////////////
//ChangeChild()函数
//交换每个结点的左右子树
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::ChangeChild()
{
    //得到当前二叉树的结点的个数
    int n=CountNode(root);
    //定义一个存放每个结点的数组w[]
    BinTreeNode<T>** w=new BinTreeNode<T>*[n];
    //把所有的结点放入数组w中去
    GetNode(w);
    //交换每个结点的左右子树
    BinTreeNode<T>* tempt;
    for(int i=0;i<n;i++)
    {
        tempt=w[i]->leftChild;
        w[i]->leftChild=w[i]->rightChild;
        w[i]->rightChild=tempt;
    }
};
/////////////////////////////ChangeChild()子树结束

//////////////////////////////////////////////////
//CreateComBinTree()公有成员函数
//通过数组w[]中的数据元素建立一棵完全二叉树
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::CreateComBinTree(T* w,int n)
{
    //定义一个结点指针数组
    BinTreeNode<T>** pw=new BinTreeNode<T>*[n];
    //把这n个数据封装成结点,并将结点指针放入数组
    cout<<endl;
    for(int i=0;i<n;i++)
        pw[i]=new BinTreeNode<T>(w[i]);
    //根据完全二叉树中父子结点中标号的关系建立二叉链表
    //左右子结点在数组中的下标
    int left,right;
    //遍历所有的分支结点
    for(i=0;i<=int(n/2)-1;i++)
    {
        //得到第i个结点的左右子结点的下标
        left=2*i+1;
        right=2*i+2;
        //把左子结点挂入第i个结点的左子树
        pw[i]->leftChild=pw[left];
        //如果有右子结点就挂入第i个结点的右子树
        if(right<=n-1)
            pw[i]->rightChild=pw[right];
    };
    //把第一个结点作为root
    root=pw[0];
};
////////////////////////CreateComBinTree()函数结束

//////////////////////////////////////////////////
//FindAcestor()私有成员函数
//找具有指定值Elem的结点的指针,并显示其所有祖先结点
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::FindAncestor(
        BinTreeNode<T>* subTree,T elem)
{
    //如果subTree不空
    if(subTree!=NULL)
    {
        //如果当前结点就含有指定元素值
        if(subTree->data==elem)
            return subTree;
        //在左右子树中进行递归搜索
        BinTreeNode<T>* pl=
            FindAncestor(subTree->leftChild,elem);
        BinTreeNode<T>* pr=
            FindAncestor(subTree->rightChild,elem);
        //如果在左子树中能找到
        if(pl!=NULL)
        {
            //显示作为父结点的当前结点
            cout<<subTree->data<<" ";
            return pl;
        }
        //如果在右子树中能找到
        else if(pr!=NULL)
        {
            //显示作为父结点的当前结点
            cout<<subTree->data<<" ";
            return pr;
        }
        else
            //返回空指针
            return NULL;        
    }
    else
        //返回空空指针
        return NULL;
};
////////////////////////////FindAncestor()函数结束