层序遍历

基本思路：利用队列，出上一层，带下一层（NULL不入队列）
（C语言需要自己构建队列→【队列】＜用链表实现队列＞ | [数据结构] | C语言）

代码

#include "Queue.h"typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);//初始化队列if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){QDataType front = QueueFront(&q);printf("%c ", front->_data);QueuePop(&q);//出一层//带下一层if (front->_left)QueuePush(&q, front->_left);if (front->_right)QueuePush(&q, front->_right);}QueueDestroy(&q);//销毁队列
}

判断完全二叉树

分步讲解

思路：层序遍历二叉树，不同的是 NULL 也要入队列。

完全二叉树出现 NULL 后面 应该全部都是 NULL

以下以一个非完全二叉树展示

上图展示的循环过程为：

QueuePush(&q, root);
while (!QueueEmpty(&q))
{QDataType front = QueueFront(&q);QueuePop(&q);//出一层if (!front)//队头遇到NULL跳出循环{break;}else{//带下一层(不管是不是空，都先把下一层放进去)QueuePush(&q, front->_left);QueuePush(&q, front->_right);}
}

• 当队头遇到NULL，不再进行入队列，而进把队列中还剩的结点依次pop出去，这个过程中如果当遇到 非NULL 就意味着该二叉树不是完全二叉树则return 0(return之后函数就结束了！开辟的空间不要忘记Destroy！)（如果把函数的返回值设为bool，就return false）
• 如果一直走到队列为空，则该二叉树是完全二叉树

while (!QueueEmpty(&q))
{QDataType front = QueueFront(&q);QueuePop(&q);//出一层if (!front){QueueDestroy(&q);//ps.开辟的空间不要忘记Destroy！return 0;}
}
QueueDestroy(&q);
return 1;

完整代码

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{assert(root);//层序遍历，如果访问到NULL后面还有数据就不是完全二叉树Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){QDataType front = QueueFront(&q);QueuePop(&q);//出一层if (!front)//队头遇到NULL跳出循环{break;}else{//带下一层(不管是不是空，都先把下一层房间去)QueuePush(&q, front->_left);QueuePush(&q, front->_right);}}while (!QueueEmpty(&q)){QDataType front = QueueFront(&q);QueuePop(&q);//出一层if (!front){QueueDestroy(&q);return 0;}}QueueDestroy(&q);return 1;
}