经典算法之层序遍历二叉树

参考：https://blog.csdn.net/wardseptember/article/details/78879360

要进行层序遍历，需要建立一个循环队列。先将二叉树头结点入队列，然后出队列，访问该结点，

如果它有左子树，则将左子树的根结点入队；

如果它有右子树，则将右子树的根结点入队。

然后出队列，对出队结点访问，如此反复，直到队列为空为止。

#include <iostream>
#include <vector>
#include <deque>using namespace std;typedef struct BTNode {char val;struct BTNode *left, *right;BTNode(char x) :val(x), left(nullptr), right(nullptr) {}
}BTNode, *BTree;//创建一棵二叉树
BTree createTree() {BTree pA = new BTNode('A');BTree pB = new BTNode('B');BTree pC = new BTNode('C');BTree pD = new BTNode('D');BTree pE = new BTNode('E');BTree pF = new BTNode('F');BTree pG = new BTNode('G');BTree pH = new BTNode('H');BTree pI = new BTNode('I');pA->left = pC;pA->right = pB;pC->left = pD;pC->right = pE;pB->right = pF;pD->left = pG;pE->right = pH;pF->left = pI;return pA;
}void levelOrderBTree(BTree pT) {if (pT != nullptr) {deque<BTNode *> que;que.push_back(pT);BTNode *q;while (!que.empty()) {q = que.front();que.pop_front();//打印节点，也可以执行其他操作cout << q->val;if (q->left != nullptr) {que.push_back(q->left);}if (q->right != nullptr) {que.push_back(q->right);}}}
}int main() {BTree pTree = createTree();cout << "层序遍历：";levelOrderBTree(pTree);cout << endl;
}