树②
_yang_yi_bo_ · · 算法·理论
众所周知，一篇总结或许需要一张头图。
二叉树的遍历
二叉树有四种遍历方法：先序遍历，中序遍历，后序遍历与层序遍历，我们先只讲前三种。
先序遍历
先序遍历的遍历顺序为根左右，也就是先遍历根节点，再遍历左子树，最后遍历右子树。
如何进行先序遍历呢？
-
我们先输出根节点
1 ，遍历左子树； -
接着输出根节点
2 ，遍历左子树； -
接着输出根节点
4 ，遍历左子树； -
接着输出根节点
7 ，由于7 没有子树，往回退； -
-
-
输出根节点
5 ，遍历左子树； -
输出根节点
8 ，8 没有子树，往回退； -
-
输出
9 往回退； -
退回到
1 ，遍历右子树； -
输出根节点
3 ，没有左子树，遍历右子树； -
输出根节点
6 ，遍历左子树； -
输出根节点
10 ，10 没有子树，一直退回到1 ； -
遍历完成，先序遍历为
1,2,4,7,5,8,9,3,6,10 。
给出 DFS 伪代码。
void dfs(int x){
输出根节点
遍历左子树
遍历右子树
}中序遍历
中序遍历的遍历顺序为左根右，也就是先遍历左子树，再遍历根节点，最后遍历右子树。
如何进行中序遍历呢？
-
遍历左子树，根节点为
2 ； -
遍历左子树，根节点为
4 ； -
遍历左子树，根节点为
7 ； -
-
往回退，输出
4 ； -
-
输出
2 ，遍历右子树，根节点为5 。 -
遍历左子树，根节点为
8 ； -
-
输出
5 ，遍历右子树； -
-
输出
1 ，遍历右子树，根节点为3 。 -
-
遍历左子树，根节点为
10 ； -
-
遍历结束，中序遍历为
7,4,2,8,5,9,1,3,10,6 。
给出 DFS 伪代码。
void dfs(int x){
遍历左子树
输出根节点
遍历右子树
}后序遍历
后序遍历的遍历顺序为左右根，也就是先遍历左子树，再遍历右子树，最后遍历根节点。
如何进行后序遍历呢？
-
遍历左子树，根节点为
2 ； -
遍历左子树，根节点为
4 ； -
遍历左子树，根节点为
7 ； -
-
-
遍历右子树，根节点为
5 ； -
遍历左子树，根节点为
8 ； -
-
遍历右子树，根节点为
9 ； -
-
输出
5 ，退回到1 ； -
遍历右子树，根节点为
3 ； -
遍历右子树，根节点为
6 ； -
遍历左子树，根节点为
10 ； -
-
输出
6 ，退回到3 ； -
输出
3 ，退回到1 ； -
输出
1 ； -
所以后序遍历为
7,4,8,5,9,2,10,6,3,1 。
给出 DFS 伪代码。
void dfs(int x){
遍历左子树
遍历右子树
输出根节点
}P1305 新二叉树
根据上面讲的内容与伪代码，模拟遍历即可。
#include<bits/stdc++.h>
using namespace std;
struct kkk{
int l,r;
}a[100005];
int n;
char st;
void dfs(int x){
if(char(x)=='*'){
return;
}cout<<char(x);
dfs(a[x].l);
dfs(a[x].r);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
char x,l,r;
cin>>x>>l>>r;
if(i==1){
st=x;
}a[x].l=l;
a[x].r=r;
}dfs(int(st));
return 0;
}P1030 [NOIP2001 普及组] 求先序排列
此题的突破口为：后序遍历时：最后一个节点为根节点。
我们可以在中序遍历中查找根节点出现的位置，输出根节点。
在中序遍历中，根节点左边的字符串为左子树的节点，根节点右边的字符串为右子树的节点。
在后续遍历中，我们设根节点前面有
一直输出当前的根节点，遍历左子树后遍历右子树就行了。
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int len1,len2;
void dfs(string s1,string s2){
if(s1.size()==0){
return;
}int len=s2.size();
int kkk=s1.size();
int pos=s1.find(s2[len-1]);
cout<<s2[len-1];
dfs(s1.substr(0,pos),s2.substr(0,pos));
dfs(s1.substr(pos+1),s2.substr(pos,kkk-pos-1));
}
int main(){
cin>>s1>>s2;
dfs(s1,s2);
return 0;
}