//////////////////////////////////////////////////
//IsCompleteBinTree()公有成员函数
//判断一棵二叉树是否是完全二叉树
//////////////////////////////////////////////////
template<class T>
bool BinaryTree<T>::IsCompleteBinTree()
{
    LinkedQueue<BinTreeNode<T>*> LQ;     //层次遍历用的队列
    LQ.EnQueue(root);                    //根结点入队列
    BinTreeNode<T>* ptr;                 //游标指针
    int flag=0;                          //0表示遍历的前个结点是数据1:表示前个是空
    while(!LQ.IsEmpty())
    {
        LQ.DeQueue(ptr);                 //从队列中取出一个元素
        
        if(ptr!=NULL)
        {
            if(flag==1)                  //如果当前是数据节点但前个是空
                return false;            //说明不是完全二叉树
            LQ.EnQueue(ptr->leftChild);  //如果是空指针也可以压入队列的
            LQ.EnQueue(ptr->rightChild);
        }
        else
            flag=1;
    };
    return true;
};
///////////////////////IsCompleteBinTree()函数结束

//////////////////////////////////////////////////
//FindWidth()公有成员函数
//求子树subTree的宽度,二叉树的宽度就是结点数最多
//的那层上的结点的个数,i是层次开始的层次数,
//count数组用于记录各层上的结点个数
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::FindWidth(BinTreeNode<T>* subTree
                             ,int* count,int i=0)
{
    if(subTree!=NULL)
    {
        cout<<++p;
        count[i]++;
        FindWidth(subTree->leftChild,count,i+1);
        FindWidth(subTree->rightChild,count,i+1);
    };
};
///////////////////////////////FindWidth()函数结束

/////////////////////////////////////////////////
//FindWidth()
//找出当前的二叉树的宽度
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::FindWidth()
{
    int dep=Height();             //当前二叉树的深度
    int* count=new int[dep];      //按照当前二叉树的深度来开辟数组
    for(int i=0;i<dep;i++)
        count[i]=0;               //把计数数组先初始化为0
    FindWidth(root,count,0);
    int max=0;
    for(i=0;i<dep;i++)            //找出最大宽度
        if(max<count[i])
            max=count[i];
    return max;
};
//////////////////////////////FindWidth()函数结束

/////////////////////////////////////////////////
//NumOfSons()公有成员函数
//递归:求解当前指定结点的所有的子孙的个数
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::NumOfSons(BinTreeNode<T>* p)
{
    if(p==NULL)                   //如果指针是空的则停止
        exit(1);
    int count=0;                  //计数器
    if(p->leftChild!=NULL)        //如果左子树不空
        count=count+1+NumOfSons(p->leftChild);
    if(p->rightChild!=NULL)
        count=count+1+NumOfSons(p->rightChild);
    return count;                 //返回子孙接点的个数
};
//////////////////////////////NumOfSons()函数结束

/////////////////////////////////////////////////
//PreOrderCount()公有成员函数
//通过前序遍历来统计当前二叉树中的结点的个数
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::PreOrderCount(
                BinTreeNode<T>* subTree)
{
    static int count=0;               //静态计数器
    if(subTree!=NULL)                 //当前结点统计加1
    {
        count++;
        if(subTree->leftChild!=NULL)  //如果左子树不空
            PreOrderCount(
                subTree->leftChild);  //递归统计左子树的结点个数
        if(subTree->rightChild!=NULL) //如果右子树不空
            PreOrderCount(
                subTree->rightChild); //递归统计右子树的结点个数
        return count;
    }
    else
        return count;
};
//////////////////////////PreOrderCount()函数结束

/////////////////////////////////////////////////
//PreOrderCreate()公有成员函数
//递归通过前序序列创建一棵二叉树，前序序列中
//空子树用符号'#'来代替,s是前序序列描述字符串
//返回的是创建结束后字符串停留的当前位置
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::PreOrderCreate(
            char* s,int start,BinTreeNode<T>*& subTree)
{
    if(s[start]!='#')          //如果当前读入的不是空子树
    {
        BinTreeNode<T>* newNode//创建新结点
            =new BinTreeNode<T>(s[start]);
        subTree=newNode;       //新建立的根结点
  
        int k=PreOrderCreate(s,//从start+1位置开始递归创建左子树
            start+1,subTree->leftChild);
        PreOrderCreate(s,k+1,  //递归创建右子树
            subTree->rightChild);
    }
    else
    {
        subTree=NULL;          //创建空子树
        return start;          //当前子树最后一个'#'
    };
};
/////////////////////////PreOrderCreate()函数结束

#endif

楼主 辛苦，写这么多 谢谢了

楼主真油！！！！谢谢分享

晕..黑压压的一片,这代码可以卖个好价钱了,呵呵...

对你的遍历真的无话说啊,我从来没这么认真的一起写过,只是偶而写一下,刚学时都是递归,但为以后找工作着想,现在改非递归了..

awesome

楼主真牛！！！你是偶的偶像