二叉树的基础遍历2.0

1.0入口：二叉树的基础遍历-CSDN博客

在1.0中使用的是简单的结构体建树，本文注重用二维vector建树。

前序，中序和后序的分析1.0已给出，本文不做过多介绍，本文重点讲二叉树的层序遍历。

先奉上前中后序的代码：

#include<bits/stdc++.h>
#define int long long 
#define endl "\n"
#define fi first
#define se second
using namespace std;
const int N=1e6+5;
vector<pair<int,int>> v[N];
void qx(int x){cout << x << " ";if(v[x][0].fi!=0) qx(v[x][0].fi);if(v[x][0].se!=0) qx(v[x][0].se);
}
void zx(int x){if(v[x][0].fi!=0) zx(v[x][0].fi);cout << x << " ";if(v[x][0].se!=0) zx(v[x][0].se);
}
void hx(int x){if(v[x][0].fi!=0) hx(v[x][0].fi);if(v[x][0].se!=0) hx(v[x][0].se);cout << x << " ";
}
void solve(){int n;cin >> n;for(int i=1;i<=n;++i){int l,r;cin >> l >> r;v[i].push_back({l,r});}qx(1);cout << endl;zx(1);cout << endl;hx(1);cout << endl;return ;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;//cin >> t;//while(t--) solve();return 0;
}

浅谈一下什么是层序遍历：层序遍历就是从左到右，一层一层的遍历。

层序遍历用递归的话有点违背递归的宗旨，递归是一直深入到某个点在回溯，而用递归每次深入就必须回退一次，如下图所示：

在这里插入图片描述

本文所用的方法为非递归（本蒟蒻不会递归的方法），非递归基于队列的实现。

首先将二叉树的根节点push到队列中
然后判断队列不为空，分别判断队首的第一个元素和第二个元素是否为空
若不为空将这些元素存入到一个数组中，并且让这些元素进队，判断完后队首出队
循环操作，直到队列为空

实现代码：

#include<bits/stdc++.h>
#define int long long 
#define endl "\n"
#define fi first
#define se second
using namespace std;
const int N=1e6+5;
vector<pair<int,int>> v[N];
pair<int,int> pa;
queue<int> q;
vector<int> ans;
void cx(int x){if(x!=0) q.push(x);ans.push_back(x); while(!q.empty()){pa=v[q.front()][0];//提取出队首if(pa.fi!=0){//判断队首的第一个元素是否为空ans.push_back(pa.fi); q.push(pa.fi);} if(pa.se!=0){//判断队首的第二个元素是否为空ans.push_back(pa.se);q.push(pa.se);	} q.pop();	}for(auto via : ans){cout << via << " ";}
}
void solve(){int n;cin >> n;for(int i=1;i<=n;++i){int l,r;cin >> l >> r;v[i].push_back(make_pair(l,r));} cx(1);return ;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;//cin >> t;//while(t--) solve();return 0;
}