前言

二叉树的层次遍历应该是数据结构里面最基础的算法了，比较容易想到的就是用队列,刚好C++的模板库里面也有queue这个数据结构，入队出队已经给我们实现好了，不然像C语言那样我估计会很烦躁哈哈哈哈。不过在学习了一下算法思路之后，我用了两种方法去实现：队列和递归。

我的思路

思路一：队列

队列真的没什么好说，首先把树的根节点入队，如果队列不为空，就弹出（输出）队首结点，然后把这个结点的左右孩子都入队。

void BreadthFirstSearch(node* root) {queue<node> myTree;if (root != nullptr) {myTree.push(*root);}while (!myTree.empty()) {cout << myTree.front().info << ' ';if (myTree.front().left != nullptr) {myTree.push(*(myTree.front().left));}if (myTree.front().right != nullptr) {myTree.push(*(myTree.front().right));}myTree.pop();}}

思路二 递归

其实这个思路的大体内容是不难的。整体来看，层次遍历也就是一层一层地输出，所以我们可以把二叉树存入一个二维数组里面，每一层都是这个二维数组的二级元素。
至于如何实现这个存储的过程，其实就需要用到BFS的思想，我们可以把层数和这个二维数组的一级元素给对应起来，比如我第一层就存储第一行数组，第二层就存储到第二行数组，依次类推。根据BFS递归的思想，每一个结点的孩子的层数都是该节点的层数+1。因此我们就很容易写出代码了。

//用于BFS递归的主函数void BFS_Recursion(node* root, int level, vector<vector<char>>& res) {if (root == nullptr) {return;}if (res.size() < level) {res.push_back(vector<char>());}res[level - 1].push_back(root->info);BFS_Recursion(root->left, level + 1, res);BFS_Recursion(root->right, level + 1, res);}void BreadthFirstSearch_recursion(node* root) {vector<vector<char>> res;BFS_Recursion(root, 1, res);for (int i = 0; i < res.size(); i++) {for (int j = 0; j < res[i].size(); j++) {cout << res[i][j] << " ";}}}

我的代码

以下是全部代码：

#include <iostream>
#include<algorithm>
#include<cmath>
#include <queue> 
using namespace std;struct node {char info;node* left;node* right;node(char data) :info(data), left(nullptr), right(nullptr) {};node() :info(NULL), left(nullptr), right(nullptr) {};
};class binaryTree {
private:node* root;
public:binaryTree() {root = new node(NULL);}//得到树的根结点node* getRoot() {return root;}//以递归的方式构建一棵树void createTree(node*& t) {char str;cin >> str;if (str == '#') {t = NULL;}else {t = new node;//为t开辟空间t->info = str;createTree(t->left);createTree(t->right);}}//树的深度int depth(node* root) {if (root == nullptr) {return 0;}int left = depth(root->left);int right = depth(root->right);return max(left, right) + 1;}//打印一棵树满二叉树，只能打印满二叉树，节点数目最好不要超过10void print(node*& root) {//存放打印的二叉树char str[10][100] = {};queue<node*> q;int h = depth(root);q.push(root);int index = 0;while (!q.empty()) {int size = q.size();//存放每一层的节点vector<char> list;for (int i = 0; i < size; i++) {node* temp = q.front();q.pop();list.push_back(temp->info);//cout << temp->info;if (temp->left != nullptr) {q.push(temp->left);}if (temp->right != nullptr) {q.push(temp->right);}}bool flag = true;int j = 0;//打印前面部分空白while (j <= 2 * h - 1 - index) {str[index][j] = ' ';j++;}//保持第一行居中if (index == 0) {for (int m = 0; m < h - 2; m++) {str[index][j++] = ' ';}}for (int k = 0; k < list.size(); k++) {//如果是一层最后一个节点if (k == list.size() - 1) {str[index][j++] = list[k];}else {//相邻左右子节点if (k % 2 == 0) {str[index][j++] = list[k];for (int l = 0; l < 3 + 2 * (h - index / 2 - 1); l++) {str[index][j++] = ' ';}}else {str[index][j++] = list[k];str[index][j++] = ' ';}}}index += 2;//cout << endl;}for (int i = 0; i < 10; i++) {if (i % 2 == 1) {for (int j = 0; j < 100; j++) {str[i][j] = ' ';}}}for (int i = 0; i < 10; i++) {if (i % 2 == 0) {for (int j = 0; j < 100; j++) {if (str[i][j] - '0' >= 0 && str[i][j] - '0' <= 9 && i < 2 * h - 2) {str[i + 1][j - 1] = '/';str[i + 1][j + 1] = '\\';}}}}for (int i = 0; i < 10; i++) {for (int j = 0; j < 100; j++) {cout << str[i][j];}cout << endl;}}void DeepFirstSearch(node* root) {if (root == NULL) {return;}else {cout << root->info << ' ';DeepFirstSearch(root->left);DeepFirstSearch(root->right);}}void BreadthFirstSearch(node* root) {queue<node> myTree;if (root != nullptr) {myTree.push(*root);}while (!myTree.empty()) {cout << myTree.front().info << ' ';if (myTree.front().left != nullptr) {myTree.push(*(myTree.front().left));}if (myTree.front().right != nullptr) {myTree.push(*(myTree.front().right));}myTree.pop();}}//用于BFS递归的主函数void BFS_Recursion(node* root, int level, vector<vector<char>>& res) {if (root == nullptr) {return;}if (res.size() < level) {res.push_back(vector<char>());}res[level - 1].push_back(root->info);BFS_Recursion(root->left, level + 1, res);BFS_Recursion(root->right, level + 1, res);}void BreadthFirstSearch_recursion(node* root) {vector<vector<char>> res;BFS_Recursion(root, 1, res);for (int i = 0; i < res.size(); i++) {for (int j = 0; j < res[i].size(); j++) {cout << res[i][j] << " ";}}}
};int main() {binaryTree T;node* root = T.getRoot();T.createTree(root);cout << "树的深度：" << T.depth(root) << endl;T.print(root);cout << "\n===========DFS recursion====================" << endl;T.DeepFirstSearch(root);cout << "\n===========BFS QUEUE====================" << endl;T.BreadthFirstSearch(root);cout << "\n===========BFS recursion====================" << endl;T.BreadthFirstSearch_recursion(root);return 0;
}

运行结果