目录
前言
二叉树的 先序遍历、中序遍历、后序遍历、层序遍历（BFS）。
一、遍历介绍
按照事先约定的某种规则或次序，对节点各访问一次而且仅一次。与向量和列表等线性结构一样，二叉树的这类访问也统称为遍历（traversal）。
二叉树本身并不具有天然的全局次序， 故为实现遍历，需通过在各节点与其孩子之间约定某种局部次序， 间接地定义某种全局次序。
按惯例左兄弟优先于右兄弟， 若记做节点 V ，及其左、右孩子 L 和 R ，则下图所示，局
部访问的次序可有 V L R 、 L V R 和 L R V 三种选择。根据节点 V 在其中的访问次序，三种策略也相应地分别称作 先序遍历、中序遍历 和 后序遍历 。
可以根据节点 V 次序位置进行记忆，先序遍历中 V 位于前端，中序遍历中 V 位于中间，后序遍历中 V 位于后端。
层序遍历是从上到下一层一层访问树的每一个节点。
二、先序遍历
通过先序遍历操作后，返回结果的顺序如下图所示。 注意下图是最终返回的结果展示顺序，实现方法及流程并非如此。
1.递归
C++代码
void preOrderRecur(Node* head) {
if (head == nullptr) {
return;
}
std::cout << head->value << ",";
preOrderRecur(head->left);
preOrderRecur(head->right);
}2.非递归
上图所示的二叉树遍历，流程描述如下：
1.从节点 a 出发，沿左分支不断深入，直至没有左分支的节点，沿途节点遇到后立即访问。首先 a 的右节点 c 直接进栈，然后访问左节点 b；
2.b 的右节点直接进栈，此时其为空节点，所以空节点进栈，访问 b 的左节点，也为空，直接进行下一步；
3.弹出栈顶空节点，再弹出 c，将 c 的右节点 f 直接进栈，并访问左节点 d；
4.将 d 的右节点 e 直接进栈，并访问左节点 ；
5.d 的左节点为空。接下来弹出栈顶的 e ，并将 e 的右节点（空节点）直接进栈，访问 e 的左节点；
6.e 的左节点为空。接下来弹出栈顶的 f ，并将 f 的右节点（空节点）直接进栈，访问 f 的左节点 g ；
7.将 g 的右节点（空节点）直接进栈， 访问 g 的左节点；
8.g 的左节点为空。弹出g 的右节点（空节点），再弹出 f 的右节点（空节点）；
9.栈为空，遍历结束。（其实上述描述的每一次循环都会做一次栈是否为空的检查）
C++代码
//先序遍历非递归
//算法步骤：
//a、根节点进栈；
//b、弹出并输出栈顶节点tp；
//c、栈顶节点tp的左孩子进栈、右孩子进栈；
//d、重复上述b、c；
void preorderTraversal(TreeNode* root) {
if (nullptr == root)
{
return;
}
stack< TreeNode*> mstack;
mstack.push(root);
while (!mstack.empty())
{
//打印栈顶节点
TreeNode* tp = mstack.top();
cout << tp->val << endl;
//弹出节点
mstack.pop();
//右孩子节点压栈
if (nullptr != tp->right)
{
mstack.push(tp->right);
}
//左孩子节点压栈
if (nullptr != tp->left)
{
mstack.push(tp->left);
}
}
return;
}
//另一解
//从当前节点出发，沿左分支不断深入，直至没有左分支的节点,沿途节点遇到后立即访问
template <typename T, typename VST> //元素类型、操作器
static void visitAlongLeftBranch(BinNodePosi(T) x, VST& visit, Stack<BinNodePosi(T)>& S) {
while (x) {
visit(x->data); //访问当前节点
S.push(x->rChild); //右孩子入栈暂存（可优化：通过判断，避免空的右孩子入栈）
x = x->lChild; //沿左分支深入一层
}
}
template <typename T, typename VST> //元素类型、操作器
void travPre_I2(BinNodePosi(T) x, VST& visit) { //二叉树先序遍历算法（迭代版）
Stack<BinNodePosi(T)> S; //辅助栈
while (true) {
visitAlongLeftBranch(x, visit, S); //从当前节点出发，逐批访问
if (S.empty()) break; //直到栈空
x = S.pop(); //弹出下一批的节点
}
}
三、中序遍历
通过中序遍历操作后，返回结果的顺序如下图所示。同样需注意下图是最终返回的结果展示顺序，实现方法及流程并非如此。
1.递归
C++代码
void inOrderRecur(Node* head) {
if (head == nullptr) {
return;
}
inOrderRecur(head->left);
std::cout << head->value << ",";
inOrderRecur(head->right);
}2.非递归
上图所示的二叉树遍历，流程描述如下：
1. 从节点 b 出发， b 进栈 S。沿左分支不断深入，遇到节点则入栈；
2.直至所有左分支节点处理完毕。（此时 S 中从上往下为 a、b）；
3.弹出栈 S 顶节点 a 并访问之；
4. 转向 a 右子树。到此处截止，为一个循环体操作。接下来对 a 右子树，对其重复循环体类似操作；
5.但这里a 右子树为空，所以继续弹出 b 。转向 b 右子树，对其进行重复循环体类似操作；
6.所以 f、d、c 依次入栈，c 在栈顶。弹出 c ，转向 c 右子树，重复循环体；
7.c 右子树为空。弹出 d ，转向 d 右子树，重复循环体。
8. e 入栈，弹出 e ，转向 c 右子树，重复循环体，c 右子树为空；
9.弹出 f，转向 f 右子树，重复循环体。
10.g 入栈， g 出栈，转向 g 右子树，为空；
11.此时，没有新的节点入栈，栈中也没有其他节点，终止遍历操作。
C++代码
//中序遍历非递归
//算法步骤：
//a、从根节点开始，整棵树的左边界节点依次进栈；
//b、弹出并输出栈顶节点tp；
//c、栈顶节点tp的右子树左边界节点依次进栈；
//d、重复上述b、c；
void inorderTraversal(TreeNode* root) {
TreeNode* tp = root;
stack< TreeNode*> mstack;
//弹出并输出栈顶节点，并对其右孩子节点压栈
while (!mstack.empty() || nullptr != tp)
{
//左边界节点依次进栈
if (nullptr != tp)
{
mstack.push(tp);
tp = tp->left;
}
else
{
//获取栈顶节点指针
tp = mstack.top();
//输出
cout << tp->val << endl;
//弹出节点
mstack.pop();
//如果有右子树，右子树的左边界节点压栈
tp = tp->right;
}
}
return;
}
//另一解
template <typename T> //从当前节点出发，沿左分支不断深入，直至没有左分支的节点
static void goAlongLeftBranch(BinNodePosi(T) x, Stack<BinNodePosi(T)>& S) {
while (x) { S.push(x); x = x->lChild; } //当前节点入栈后随即向左侧分支深入，迭代直到无左孩子
}
template <typename T, typename VST> //元素类型、操作器
void travIn_I1(BinNodePosi(T) x, VST& visit) { //二叉树中序遍历算法（迭代版）
Stack<BinNodePosi(T)> S; //辅助栈
while (true) {
goAlongLeftBranch(x, S); //从当前节点出发，逐批入栈
if (S.empty()) break; //直至所有节点处理完毕
x = S.pop(); visit(x->data); //弹出栈顶节点并访问之
x = x->rChild; //转向右子树
}
}四、后序遍历
通过后序遍历操作后，返回结果的顺序如下图所示。
1.递归
C++代码
void posOrderRecur(Node* head) {
if (head == nullptr) {
return;
}
posOrderRecur(head->left);
posOrderRecur(head->right);
std::cout << head->value << ",";
}2.非递归
上图所示的二叉树遍历，流程描述如下：
1.找到最高左侧可见叶节点 k，若有右子树优先入栈（此处为 j），但优先往左子树方向走（i 入栈）；
2.i 的右子树 h 入栈，i 无左子树，所以继续对右子树 h 进行操作；
3.h 的右子树 g 入栈，方向到左子树（b 入栈）；
4.b 的右子树 a 入栈，b 无左子树。继续对 a 进行操作，a 无子节点；
5.到此为止，第一次入栈操作结束，此时栈中顶而下依次为 abghijk；
6.接下来弹出栈顶元素 a ，访问之；
7.b 是 a 的父节点，不用进行 入栈操作。弹出栈顶元素 b ，访问之；
8.接下来是 g ，非 b 的父节点，执行入栈操作，按照1~5步骤说的方法，依次将 fedc 入栈；
9.接下来判断是否需要执行入栈，并不断从栈中弹出节点，并访问之；
10.最后，栈为空，遍历结束。
C++代码
//后序遍历非递归
//算法步骤：
//申请两个栈，s1，s2
//a、根节点入栈s1;
//b、弹出（不输出）栈顶节点tp，压入栈s2；
//c、栈顶节点tp的左孩子、右孩子依次进栈s1；
//d、重复上述b、c，直到栈s1为空，所有节点进入栈s2；
//e、依次弹出并输出栈s2栈顶节点；
void postorderTraversal(TreeNode* root) {
//根节点为空，直接返回
if (nullptr == root)
{
return;
}
//申请2个栈
stack< TreeNode*> s1, s2;
//根节点压入s1
s1.push(root);
while (!s1.empty())
{
TreeNode* tp = s1.top();
s2.push(tp);
s1.pop();
if (nullptr != tp->left)
{
s1.push(tp->left);
}
if (nullptr != tp->right)
{
s1.push(tp->right);
}
}
//依次弹出并输出s2节点
while (!s2.empty())
{
cout << s2.top()->val << endl;
s2.pop();
}
return;
}
//另一解
template <typename T> //在以S栈顶节点为根的子树中，找到最高左侧可见叶节点
static void gotoHLVFL(Stack<BinNodePosi(T)>& S) { //沿途所遇节点依次入栈
while (BinNodePosi(T) x = S.top()) //自顶而下，反复检查当前节点（即栈顶）
if (HasLChild(*x)) { //尽可能向左
if (HasRChild(*x)) S.push(x->rChild); //若有右孩子，优先入栈
S.push(x->lChild); //然后才转至左孩子
} else //实不得已
S.push(x->rChild); //才向右
S.pop(); //返回之前，弹出栈顶的空节点
}
template <typename T, typename VST>
void travPost_I(BinNodePosi(T) x, VST& visit) { //二叉树的后序遍历（迭代版）
Stack<BinNodePosi(T)> S; //辅助栈
if (x) S.push(x); //根节点入栈
while (!S.empty()) {
if (S.top() != x->parent) //若栈顶非当前节点之父（则必为其右兄），此时需
gotoHLVFL(S); //在以其右兄为根之子树中，找到HLVFL（相当于递归深入其中）
x = S.pop(); visit(x->data); //弹出栈顶（即前一节点之后继），并访问之
}
}五、层序遍历
C++代码
//层序遍历
//一般基于队列的实现:
//a、将二叉树的根节点push到队列中。
//b、判断队列不为空就输出队头元素。
//c、判断当前对头节点是否有孩子节点，有则push到队列中。
//循环操作b、c，直到队列为空。
void FloorPrint_QUEUE(TreeNode* Tree) //层序遍历_队列实现
{
queue < TreeNode* > q;
if (Tree != nullptr)
q.push(Tree); //根节点进队列
while (!q.empty()) //队列不为空
{
TreeNode* node=q.front();
cout << node->val;
if (node->left != nullptr) //如果有左孩子，入队
q.push(node->left);
if (node->right != nullptr) //如果有右孩子，入队
q.push(node->right);
q.pop(); //已经遍历过的节点出队列
}
}六、参考文献
1.[算法] 二叉树的 先序遍历、中序遍历、后序遍历_scxyz_的博客-CSDN博客_中序遍历算法
2.二叉树的先序、中序、后序遍历C++_星星典典的博客-CSDN博客_c++二叉树的先序,中序,后序遍历
评论（0）
您还未登录，请登录后发表或查看评论