二叉树的遍历（递归、非递归的前中后序遍历和层序遍历）

二叉树的遍历（递归、非递归的前中后序遍历和层序遍历） 二叉树相关

最近在重新学习数据结构，感觉之前学二叉树遍历总是一知半解，现在又重新整理了相关代码和思路，以下是我的一些理解。

文章目录

• 二叉树相关
• • 1.手写遍历和递归的代码实现
  • • 1.1手写二叉树的遍历的方法
    • 1.2 二叉树遍历递归方法的代码实现
  • 2. 非递归遍历的代码实现
  • • 2.1前序遍历
    • 2.2 后序遍历
    • 2.3 中序遍历
    • 3. 二叉树的层序遍历

1.手写遍历和递归的代码实现 1.1手写二叉树的遍历的方法

以前序遍历为例，它的顺序是“根左右”，一定要记清楚，根指的是根节点，左指的是左子树，右指的是右子树；意思是首先遍历到根节点，然后遍历根节点对应的左子树，再后遍历根节点对应的右子树；递归的思想就是，对左子树和右子树也按照“根左右”顺序进行遍历，直到所有节点遍历完成。
如下图，展示了前序遍历的过程，其中左子树用黄色表示，右子树用绿色表示，根节点用黑色表示,这就是一个典型的递归，终止条件是根节点为空，将每次遍历到的根节点按照相对顺序写出来就是前序遍历。

下图展示了中序遍历的过程，不同之处就是顺序，中序遍历的顺序是左根右，依旧是每次输出根节点，只是左右子树输出的相对顺序发生了改变：
用上面的方法就可以手写得出二叉树的前中后序遍历（后序遍历思路同前，区别是顺序是左右根）。

1.2 二叉树遍历递归方法的代码实现

编程实现的思路是递归，因此相应的代码如下，每次递归执行输出根节点，终止条件是根节点为空。
二叉树数据结构的定义

//二叉树的节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
 };

代码的区别仅仅在于根、左、右三句代码实现的顺序上。如果仅仅只要输出结果，代码如下：

void preorderTraversal(TreeNode* root)//前序遍历
{
    if(!root)return;//递归终止条件：根为空
    cout<val<<" ";//每次递归的行为：输出根节点
    if(root->left)preorderTraversal(root->left);//先遍历左子树
    if(root->right)preorderTraversal(root->right);//再遍历右子树
}
void inorderTraversal(TreeNode* root)//中序遍历
{
    if(!root)return;//递归终止条件：根为空
    if(root->left)inorderTraversal(root->left);//先遍历左子树
    cout<val<<" ";//每次递归的行为：输出根节点
    if(root->right)inorderTraversal(root->right);//再遍历右子树
}
void postorderTraversal(TreeNode* root)//后序遍历
{
    if(!root)return;//递归终止条件：根为空
    if(root->left)postorderTraversal(root->left);//先遍历左子树
    if(root->right)postorderTraversal(root->right);//再遍历右子树
    cout<val<<" ";//每次递归的行为：输出根节点
}

如果想要将遍历的结果以数组的方式储存起来，代码实现略微复杂，需要一个帮助函数，每次的输出根节点的行为变成将根节点放入数组中去，代码如下：

//前序遍历
void preorderTraversal_help(TreeNode* root,vector&ans){//帮助函数
    if(root==NULL)return;
    ans.push_back(root->val);//每次递归的行为变成将根节点放入栈中
    if(root->left!=NULL)preorderTraversal_help(root->left,ans);
    if(root->right!=NULL)preorderTraversal_help(root->right,ans);
}
vector preorderTraversal(TreeNode* root){//核心函数
    vectorans;
    preorderTraversal_help(root,ans);
    return ans;
}

2. 非递归遍历的代码实现

不用递归的方法就是用栈（放二叉树的节点），前序和后序遍历的非递归算法比较类似，放在一起总结。

2.1前序遍历

思路分为两部分：
1.根节点入栈
2.1栈顶节点的值放入结果数组中，并出栈
2.2前栈顶节点的右节点、左节点依次入栈
循环2.1 2.2 直到栈为空
下图展示了该二叉树前序遍历时栈的变化过程：

代码如下：

//前序遍历的非递归代码写法
vector preorderTraversal(TreeNode* root){
    vectorans;//存放遍历结果的数组
    stacks;//用来存放节点的栈
    s.push(root);// 1.根节点入栈
    while(!s.empty()){
        TreeNode* cur=s.top();//2.1栈顶节点
        ans.push_back(cur->val);//2.1栈顶节点的值放入结果数组
        s.pop();//2.1栈顶元素出栈
        if(cur->right)s.push(cur->right);//2.2前栈顶元素右节点入栈
        if(cur->left)s.push(cur->left);//2.2前栈顶元素左节点入栈
    }
    return ans; 
}

2.2 后序遍历

后序遍历和前序遍历的非递归写法思路非常相同，仅仅区别在于2.2左右节点入栈的顺序 ，多步骤3的元素倒序。
1.根节点入栈
2.1栈顶节点的值放入结果数组中，并出栈
2.2前栈顶元素的左节点、右节点依次入栈
循环2.1 2.2，直到栈为空
3.结果数组元素倒序
下图展示了该二叉树后序遍历时栈的变化过程：

代码如下：

//后序遍历的非递归代码写法
vector postorderTraversal(TreeNode* root){
    vectorans;
    if(!root)return ans;
    stacks;
    s.push(root);//1.根节点入栈
    while(!s.empty()){
        TreeNode* cur=s.top();
        ans.push_back(cur->val);//2.1栈顶节点的值放入结果数组中
        s.pop();//2.1出栈
        if(cur->left)s.push(cur->left);//2,22.2前栈顶元素的左、右节点依次入栈
        if(cur->right)s.push(cur->right);
    }
    reverse(ans.begin(),ans.end()); 
    return ans;
}

2.3 中序遍历

中序遍历的思路比较不同，实际上中序遍历可以理解为二叉树在水平方向上的投影，因此越靠左的节点越先遍历到，思路的核心就是每次找最左边的节点。

思路分为两部分：
1 将根节点设为当前节点
2.1 找当前节点的最左节点：当前节点的左节点依次入栈，当前 节点置左cur=cur->left,直到左节点为空
2.2 当前节点更新为栈顶节点，值放入结果数组中，当前节点置右cur=cur->right,出栈
循环2.1 2.2 直到栈为空且cur为空
下图展示了该以上一节二叉树为例的中序遍历时栈的变化过程

代码如下：

//中序遍历的非递归写法
vector inorderTraversal2(TreeNode* root){
    vectorans;
    if (root == NULL)return ans;
	TreeNode* cur = root;//1.根节点设为当前节点
	stack s;
	while (!s.empty() || cur){
		while (cur){//2.1找当前节点的最左节点：直到当前节点为空
			s.push(cur);//2.1当前节点的左节点依次入栈
			cur=cur->left;//2.1当前节点置为左节点
		}
		if (!s.empty()){//，出栈，值输出，cur=cur->right
			cur = s.top();//2.2当前节点返回到栈顶节点
			ans.push_back(cur->val);//2.2值输出到结果数组
			cur=cur->right;//2.2当前节点置右
			s.pop();//2.2d出栈顶节点
		}
	}
	return ans;
}

3. 二叉树的层序遍历

二叉树的层序遍历利用队列的数据结构非常简单，思路如下
1 根节点入队
2.1 队首节点的值输出到结果数组中
2.2 队首节点的左右节点依次入队
2.3 队首节点出队
循环2.1 2.2 2.3 直到队为空
下图展示了该以上一节二叉树为例的层序遍历时栈的变化过程
代码如下：

//层序遍历
vector orderTraversal(TreeNode* root){
    vectorans;
    if(!root)return ans;
    queueq;
    q.push(root);//1 根节点入队
    while(!q.empty()){
        ans.push_back(q.front()->val);//2.1队首节点的值输出到结果数组中
        if(q.front()->left)q.push(q.front()->left);//2.2队首节点的左右节点依次入队
        if(q.front()->right)q.push(q.front()->right);//2.2队首节点的左右节点依次入队
        q.pop();//2.3队首元素出队
    }
    return ans;
}