1.层序遍历

层序遍历:层序遍历即逐层按顺序遍历二叉树的各个节点,故层序遍历又叫广度优先遍历.
如图:广度优先遍历即按ABCDEFGH的顺序遍历

2.解题思路

1.这里我们利用队列先进先出的结构特点,当我们在队列中弹出一个树的节点时,我们便把树的左孩子和右孩子入到队列之中.(如果父节点的左右孩子为空时,我们便可不对其孩子进行入队列操作)
2.根据上面描述,我们可以用一个while循环解决入队列与出队列操作,结束条件便是判断队列是否为空.

3.代码实现

我们用C语言实现时,我们得自己写一个队列的结构,该结构能实现判空,入队,出队的操作,这里主要以实现层序遍历为主.省略了队列的那一部分代码.

typedef struct BinaryTreeNode {struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType val;
}BTNode;void BT_LayerTraversal(BTNode* root) {Queue Q;QueueInit(&Q);//!root 可以理解为 root == NULLif (!root) {printf("该二叉树为空!\n");return;}//在进入循环之前我们得手动将头结点入队QueuePush(&Q , root);while ( !QueueEmpty(&Q) ) {//用cur记录父节点的信息,方便后序对子节点入队.BTNode* cur = QueueFront(&Q);printf("%c ",cur->val);QueuePop(&Q);//如果左右子树不为空,入左右子树if (cur->left) QueuePush(&Q ,cur->left); if (cur->right)QueuePush(&Q, cur->right);}