博客

以下两种思路都为层序遍历：

第一种思路，找到第一个不饱和节点（节点不为空，但节点只有左子节点||只有右子节点||没有子节点），在该节点之后的节点都没有子节点，即为完全二叉树。

第二种思路，找到第一个空节点（节点为NULL），之后队列中的节点都为NULL，即为完全二叉树。（该思路在遍历的过程中节点的左右子节点无论是否为空都要入队）

下面给出第二种思路（相较第一种思路代码较为简洁）的代码实现，使用循环数组模拟队列：

int IsComplete(BinTree T)
{
    if (T == NULL) {
        return 1; //1代表 是完全二叉树
    }
    BinTree queue[50009];
    int maxSize = 50000;
    int front = -1;
    int end = -1;
    end = (end + 1) % maxSize;
    queue[end] = T;
    while (front != end) {
        front = (front + 1) % maxSize;
        BinTree cur = queue[front];
        if (cur == NULL) {
            break;
        } else {
            end = (end + 1) % maxSize;
            queue[end] = cur->Left;
            end = (end + 1) % maxSize;
            queue[end] = cur->Right;
        }
    }
    int ans = 1;
    while (front != end) {
        front = (front + 1) % maxSize;
        if (queue[front] != NULL) {
            ans = 0;
        }
    }
    return ans;
}