【数据结构】二叉树遍历(前序/中序/后序/层序-递归与非递归)
「前言」
🌈个人主页: 代码探秘者
🌈C语言专栏:C语言
🌈C++专栏: C++ / STL使用以及模拟实现
🌈数据结构专栏: 数据结构 / 十大排序算法
🌈Linux专栏: Linux系统编程 / Linux网络编程(准备更新)
🌈喜欢的诗句:天行健,君子以自强不息.
二叉树的遍历是指按某条搜索路径访问树中的每个结点,使得每个结点均被访问一次,而且仅能访问一次(说明不可二次访问,一遍而过)。
- 遍历一颗二叉树便要决定对根结点N、左子树L和右子树的访问顺序。
- 二叉树常的的遍历方法有=前序遍历、中序遍历和后序遍历三种遍历算法,三种遍历方法有递归和非递归两个版本。
- 当然还有层序遍历
一、前序遍历
力扣链接:二叉树前序遍历
递归版本
前序遍历的算法思路:
若二叉树为空,什么都不做,否则:
i、先访问根结点;
ii、再前序遍历左子树;
iii、最后前序遍历右子树;
简单版本的实现:
void preorder(TreeNode* root)
{
//递归结束条件/空树
if(root==nullptr)
return;
cout<<root->val<<" "; //访问根
preorder(root->left,v); //访问左
preorder(root->right,v); //访问右
}
非递归版本 (重要)
前序遍历的非递归算法,即利用一个栈,来进行访问结点并入栈遍历左子树,结点出栈遍历右子树。
1. 思路
算法思路:
1、二叉树为空啥也不做;
2、结点不为空,访问(把遍历结果保存)并入栈,,遍历其左子树;
3、栈顶元素出栈,遍历栈顶元素的右子树(循环又回来,如果它还有左子树,继续入完);
4、结点为空并且栈为空结束遍历。
2. 图解
图解前序遍历的递归算法:
咱们看下面的二叉树是怎样利用递归函数实现前序遍历:
📖入栈步骤核心:
先访问,再入栈,如果访问节点的左子树不为空,再继续访问(左子树的左子树…),一直入完左路节点为止,才能开始出栈
//访问(把遍历结果保存)并入栈,把左子树节点入完
while(cur)
{
v.push_back(cur->val); //遍历(保存)
st.push(cur);
cur=cur->left; //左孩子不为空,一直往左走
}
不为空树,cur != nullptr,访问(把遍历结果保存)A,并入栈A
A的左子树不为空,遍历B,并将B入栈,遍历B的左子树:
B的左子树不为空,遍历D,并将D入栈,遍历D的左子树:
下面可以看到,D无左子树,其本身都遍历完。
📖出栈步骤核心:
先取栈顶元素出栈,如果出栈元素的右子树不为空,要访问继续访问它的右子树,进入下一轮循环(先访问它右子树的左子树…)
先出D,访问右子树,但是显然没有右子树
然后B出栈,遍历B的右子树E
访问E,入栈
E的左子树不为空,遍历G,G入栈,遍历G的左子树(显然为空,右子树也为空)
G的左子树为空,不遍历,G出栈遍历G的右子树,但G的右子树为空,故也不进行遍历:
此时,栈中有E、A结点,E出栈,遍历E的右子树,但E的右子树为空,故不进行遍历:
然后A出栈,A的右子树不为空,遍历A的右子树:
遍历C,C入栈,遍历C的左子树:
C的左子树为空,不遍历,C出栈,遍历C的右子树:
遍历F,F入栈,遍历F的左子树:
F的左子树为空,不遍历,F出栈,遍历F的右子树:
F的右子树为空,不遍历,此时栈为空,结束遍历,二叉树的全部结点有且仅有一次被访问:
前序遍历的结果为:
3. 代码
算法实现:
vector<int> preorderTraversal(TreeNode* root)
{
//空树
if(root==nullptr)
return {};
//开始遍历
TreeNode* cur=root; //遍历指针
vector<int> v; //遍历结果保存在这里
stack<TreeNode*> st; //用栈来完成遍历
while(cur||!st.empty()) //遍历指针不为空或者栈不为空
{
//访问(把遍历结果保存)并入栈,把左子树节点入完
while(cur)
{
v.push_back(cur->val); //遍历(保存)
st.push(cur);
cur=cur->left; //左孩子不为空,一直往左走
}
//访问左路节点的右子树
TreeNode* top=st.top();
st.pop();
cur=top->right; //遍历它的右子树(不为空时)
}
return v;
}
二、中序遍历
力扣链接:二叉树中序遍历
递归版本
中序遍历算法思路:
二叉树为空,什么也不做,否则:
i、中序遍历左子树;
ii、访问根结点;
iii、中序遍历右子树
简单版本的实现:
void inorder(TreeNode* root)
{
//递归结束条件/空树
if(root==nullptr)
return;
preorder(root->left,v); //访问左
cout<<root->val<<" "; //访问根
preorder(root->right,v); //访问右
}
非递归版本
1.思路
中序遍历的非递归算法,就是将上面递归函数隐式调用栈的过程给显示表示出来,即利用一个辅助栈,来进行结点入栈访问结点的左子树,出栈访问结点,并且遍历结点的右子树。
算法思路:
1、二叉树为空,啥也不做
2、结点不为空,入栈,并遍历其左子树
3、结点的左子树为空但栈不为空,栈顶元素出栈并访问,接着遍历栈顶元素的右子树;
4、栈为空,且结点也为空结束遍历。
2.代码
下面是前序非递归的代码
这里是中序非递归的代码,其实没变化什么,就访问时间发生变化
vector<int> preorderTraversal(TreeNode* root)
{
//空树
if(root==nullptr)
return {};
//开始遍历
TreeNode* cur=root; //遍历指针
vector<int> v; //遍历结果保存在这里
stack<TreeNode*> st; //用栈来完成遍历
while(cur||!st.empty()) //遍历指针不为空或者栈不为空
{
//访问(把遍历结果保存)并入栈,把左子树节点入完
while(cur)
{
v.push_back(cur->val); //遍历(保存)
st.push(cur);
cur=cur->left; //左孩子不为空,一直往左走
}
//访问左路节点的右子树
TreeNode* top=st.top();
st.pop();
cur=top->right; //遍历它的右子树(不为空时)
}
return v;
}
三、后序遍历
力扣连接:二叉树的后序遍历
递归版本
算法思路:
若二叉树为空,什么也不做,否则:
i、后序遍历左子树
ii、后序遍历右子树
iii、访问根结点
算法实现:
void preorder(TreeNode* root)
{
//递归结束条件/空树
if(root==nullptr)
return;
preorder(root->left,v); //访问左
preorder(root->right,v); //访问右
cout<<root->val<<" "; //访问根
}
非递归版本 (难+重要)
1. 思路
- 当二叉树为空,则什么也不做;
- 结点不为空,先入左路节点
- prev:记录访问的上一个节点
- 出栈条件:右子树为空或者top->right=prev(说明右子树已经访问完)
- 如果右子树不为空,top->right!=prev(右子树没有访问完),得访问其右子树,不能出栈
- 出栈+访问,更新prev(记录访问的上一个节点)
2. 图解
为了简单了解思想,我这里演示遍历这个树(这里只有树的一半,不过已经够了哦)
📖 tip1
- 先入左路节点
📖 tip2
- 这里重要细节,我用一个prev指针保存前一个访问的节点
开始出栈:D没有左右节点,直接出,遍历
📖 tip3
这里B不能直接出,为什么?
- 得访问B的右路节点,所以得继续入栈.
B什么时候能出?
- top->right=prev(核心)
- 就是E出了下一个B才能出哦
下面分别入E、以及它的左路节点G。
出G
📖 tip4 - 访问节点,记得更新prev(上个一个访问的结点)
出E
📖 tip5
- 这里B可以出栈,因为top->right=prev
- 这是后序非递归区别前中序的非递归的核心步骤
A再出栈
完成遍历(这里我值演示了遍历整个树的左子树)
遍历结果:D->G->E->B->A
3. 代码
vector<int> postorderTraversal(TreeNode* root) {
//空树
if(root==nullptr)
return {};
//开始遍历
TreeNode* cur=root; //遍历指针
TreeNode* prev=root; //记录前一个被访问节点
… //访问左路节点的右子树
TreeNode* top=st.top();
//出栈要求:
//1.右子树为空。
//2.或者top->right==prev(就是说B前面一个访问节点是E)
if(top->right==nullptr||top->right==prev)
{
st.pop();
v.push_back(top->val); //访问(保存)
prev=top; //更新prev
}
else
{
cur=top->right; //遍历它的右子树(不为空时)
}
}
return v;
}
运行结果:
四、层序遍历
1. 思路
顾名思义,对于树型结构,层序遍历就是按层从上到下,每层按一定顺序对树的节点进行遍历。我们通过如图所示的二叉树进行说明:对于左边的二叉树,按层划分后可得到右边的分层结构。
这个树层序结果就是:1 4 2 7 20 5
2. 图解
- 创建一个队列(根节点入队)
- 取队头元素,出队
- 如果队头元素有左、右孩子,就依次入队
- 队列为空,遍历结束
先入根结点
删1,把左右孩子4,2 带进来
此时遍历结果为:1
删4,把左右孩子7,20 带进来
此时遍历结果为:1 4
删2,把左孩子5 带进来
此时遍历结果为:1 4 2
之后依次删吧
队列为空,遍历完成!
此时遍历结果为:1 4 2 7 20 5
3. 代码
void levelOrder(TreeNode* root)
{
//边界情况:空树
if(root==nullptr)
return {};
queue<TreeNode*> q; //队列
q.push(root); //先入根结点
while(!q.empty())
{
//出队列,并且让他们孩子入队
TreeNode* front=q.front();
q.pop();
//访问结点
cout<<front->val<<" ";
//入左节点
if(front->left)
q.push(front->left);
//入右节点
if(front->right)
q.push(front->right);
}
}
4. 力扣:层序遍历
下面是一个力扣层序遍历题:
力扣链接:层序遍历
要求把遍历结果放二维数组返回,每行就是每层遍历的结果
vector<vector<int>> levelOrder(TreeNode* root) {
//边界情况
if(root==nullptr)
return {};
vector<vector<int>> vv; //保存所有的遍历结果
queue<TreeNode*> q;
q.push(root);
//第一层只有一个孩子
int LevelSize=1;
while(!q.empty())
{
vector<int> v; //保存每层的数据
//记录每层有多少个孩子
while(LevelSize--)
{
//出队列,并且让他们孩子入队
TreeNode* front=q.front();
q.pop();
v.push_back(front->val);
//入左节点
if(front->left)
q.push(front->left);
//入右节点
if(front->right)
q.push(front->right);
}
LevelSize=q.size(); //更新每层孩子个数
vv.push_back(v); //把每层的访问数据插入二维数组
}
return vv;
}
5. 力扣:锯齿形层次遍历
力扣链接
- 即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行
在原来层序遍历的基础上,加间隔一层反转
reverse(v.begin(),v.end());
思路:
代码
vector<vector<int>> zigzagLevelOrder(TreeNode* root)
{
//边界情况:空树
if(root==nullptr)
return {};
vector<vector<int>> vv; //保存所有的遍历结果
queue<TreeNode*> q;
q.push(root);
bool flag=false;
//第一层只有一个孩子
int LevelSize=1;
while(!q.empty())
{
vector<int> v; //保存每层的数据
//记录每层有多少个孩子
while(LevelSize--)
{
//出队列,并且让他们孩子入队
TreeNode* front=q.front();
q.pop();
v.push_back(front->val);
//入左节点
if(front->left)
q.push(front->left);
//入右节点
if(front->right)
q.push(front->right);
}
LevelSize=q.size(); //更新每层孩子个数
//判断是不是要反转
if(flag)
reverse(v.begin(),v.end());
vv.push_back(v); //把每层的访问数据插入二维数组
flag=!flag; //间隔一层反转
}
return vv;
}