判断是否为完全二叉树

分析

1.完全二叉树的概念：对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

2.思路：可以采用层序遍历的方法，把节点依次放入队列中，空节点也要放进去，在出队列的时候，出到空了，就开始遍历整个队列，如果整个队列都是空节点，则是完全二叉树，遇到非空节点，就不是完全二叉树。
注意：那会不会出现有些非空节点还没有进队列，就已经开始判断是否有非空节点？
当然，这种情况是不会存在的。
后面非空节点一定是前面非空节点的孩子，前面非空节点已经出了队列，那么后面的非空节点肯定也已经入了队列

3.代码

bool TreeComplete(BTNode* root)
{Queue q;//创建队列QueueInit(&q);//队列的初始化QueuePush(&q, root);//将根节点进到队列中while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);//取出队头的数据，判断对头是否为空，为空的话，我们就可以不用出队列了，直接访问剩下的队列的数据if (front == NULL){break;}QueuePop(&q);//出对头数据QueuePush(&q, front->left);//进左孩子QueuePush(&q, front->right);//进右孩子}//继续判断接下来的队列数据是否有非空的节点，有的话，就不是完全二叉树。while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);{if (front){QueueDestroy(&q);return false;}}QueuePop(&q);}QueueDestroy(&q);return true;
}

这里我没有写队列的数据结构，我是写好了，直接拿来用的。