一、队列知识补充
有关队列的知识请详见博主的另一篇博客：http://t.csdnimg.cn/3PwO4
本文仅仅附上需要的队列操作供读者参考
//结构体定义
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
//入队
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = InitNewnode(x);
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
//出队
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* temp = pq->phead->next;
free(pq->phead);
pq->phead = temp;
}
pq->size--;
}
//取出队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* pcur = pq->phead;
while (pcur)
{
QNode* temp = pcur->next;
free(pcur);
pcur = temp;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}二、层序遍历
2.1 递归思路
采用队列先进先出的特点，按照层序入队即可按照层序出队，从而达到层序遍历的目的。
考虑一般情况：
将根节点入队，下一次根节点出队的同时将孩子结点入队。
考虑特殊情况：
孩子结点可看作子树的根节点，重复递归即可。
只要队列不为空就一直递归
2.2 图解
2.3 C语言实现
注意：出队入队要额外新建变量来复制结点，避免销毁队列引发的原二叉树丢失的问题。
void TreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (QueueEmpty(&q)==false)
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
QueueDestroy(&q);
}三、判断一棵树是不是完全二叉树
3.0 回顾
什么是完全二叉树？完全二叉树是一种特殊的二叉树，其中除了最后一层外，每一层的节点都被填满，而且最后一层的节点都尽可能地靠左排列。换句话说，如果一个层次深度为k的树，除了第 k 层外，其他各层都是满的，并且第 k 层的节点都依次靠左排列，则这棵树就是完全二叉树。
所以仅仅通过判断结点的范围处于k-1层满二叉树和k层满二叉树之间的解法是错误的！！
3.1 思路
通过层序遍历，将第一次出现空结点的地方找到，只需判断后续遍历的过程中是否存在非空结点即可，若存在就不是完全二叉树，反之则是。
分两个循环解决该问题。
- 第一层循环本质即为层序遍历，找到第一个空节点就退出。
- 第二层循环依然为层序遍历，看是否可以找到非空结点。当队列里面没有元素即层序遍历结束时判断完成。
3.2 C语言实现
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root != NULL)
{
QueuePush(&q, root);
}
//入队遇到空停止入队
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
break;
}
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
//判断后面是否还有非空
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
return false;
}
}
QueueDestroy(&q);
return true;
}
