B3642 二叉树的遍历＜---搜索与树

书接上级：

题目来源

B3642 二叉树的遍历 - 洛谷

题目描述

有一个 n(n≤106) 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 n），建立一棵二叉树（根节点的编号为 1），如果是叶子结点，则输入0 0。

建好树这棵二叉树之后，依次求出它的前序、中序、后序列遍历。

输入格式

第一行一个整数 n，表示结点数。

之后 n 行，第 i 行两个整数 l、r，分别表示结点 i 的左右子结点编号。若 l=0 则表示无左子结点，r=0 同理。

输出格式

输出三行，每行 n 个数字，用空格隔开。

第一行是这个二叉树的前序遍历。

第二行是这个二叉树的中序遍历。

第三行是这个二叉树的后序遍历。

输入输出样例

输入 #1

7 2 7 4 0 0 0 0 3 0 0 0 5 6 0

输出 #1

1 2 4 3 7 6 5 4 3 2 1 6 5 7 3 4 2 5 6 7 1

题目分析

这道题根据树的遍历可以分成三部分，为前序遍历，中序遍历，后序遍历。

遍历详情见：有关树的存储与二叉树的遍历-CSDN博客

前序遍历为根左右。

先输出自己，再输出左，然后返回到右

而中序遍历，则为判断自己的左节点是否遍历过了或是否为空，等自己左节点为空或被遍历后，输出自己，然后再看右节点。

最后后序遍历，用while循环，根节点的左与右节点都被遍历后或都为0时，则结束，否则执行while循环，如果自己的左与右节点都输出过或为空，则输出自己，标记自己。

代码

#include<bits/stdc++.h> using namespace std; const int maxn=1e6+5; vector<int> t[maxn]; bool p[maxn];//中序遍历的标记数组 bool st[maxn];//后序遍历的标记数组 int x1[maxn]; void dfs(int m) { if(m!=0) cout<<m<<" "; for(int i=0; i<t[m].size(); i++) { dfs(t[m][i]); } } void z(int m) { if(p[t[m][0]]==false) { cout<<m<<" "; p[m]=false; if(p[t[m][1]]!=false) { z(t[m][1]); } return; } for(int i=0; i<t[m].size(); i++) { if(i==0) { if(p[t[m][i]]!=false) { z(t[m][i]); } } if(p[m]!=false){ cout<<m<<" "; p[m]=false; } if(i==1){ if(p[t[m][i]]!=false) { z(t[m][i]); } } } } int main() { int n; cin>>n; for(int i=1; i<=n; i++) { st[i]=true; p[i]=true; } for(int i=1; i<=n; i++) { int l,r; cin>>l>>r; t[i].push_back(l); t[i].push_back(r); } dfs(1);//前序遍历 cout<<endl; z(1);//中序遍历 cout<<endl; int j=0; int x=1; x1[j]=x; while(st[t[1][0]]!=false||st[t[1][1]]!=false) { if(st[t[x][0]]==false&&st[t[x][1]]==false) { cout<<x<<" "; st[x]=false; while((st[t[x][0]]==false&&st[t[x][1]]==false)&&x!=1) { x=x1[--j];//返回 } } else { for(int i=0; i<t[x].size(); i++) { if(st[t[x][i]]!=false) { x=t[x][i]; x1[++j]=x; break; } } } }//后序遍历 cout<<1;//输出根节点 return 0; }