设置时间戳，判断

写出代码还需要继续斟酌...

[[it] 本帖最后由 geninsf009 于 2008-10-17 22:21 编辑 [/it]]

missiyou兄高见，高见啊~！这个方法不错，我已经按照你的思路把代码写好了，已经测试通过了，
代码如下：
//////////////////////////////////////////////////
//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()函数结束

我觉得时间复杂度并不坏，这个利用的是层次遍历，只是多把其中一些结点的空指针也压入队列了，
时间复杂度在最坏的情况下是o(2*n+1），还好是线性关系的...

你好,我错了
BS一下自已..

[quote][bo][un]很远的那颗星[/un] 在 2008-10-17 21:10 的发言：[/bo]


详细一点嘛~~~
[quote]
奇怪，昨天明明写了的啊。
层次遍历，出现结点有空孩子就设置标记，如果之后出现某结点有子结点则说明不是完全二叉树。