书接上级题目来源B3642 二叉树的遍历 - 洛谷题目描述有一个 n(n≤106) 个结点的二叉树。给出每个结点的两个子结点编号均不超过 n建立一棵二叉树根节点的编号为 1如果是叶子结点则输入0 0。建好树这棵二叉树之后依次求出它的前序、中序、后序列遍历。输入格式第一行一个整数 n表示结点数。之后 n 行第 i 行两个整数 l、r分别表示结点 i 的左右子结点编号。若 l0 则表示无左子结点r0 同理。输出格式输出三行每行 n 个数字用空格隔开。第一行是这个二叉树的前序遍历。第二行是这个二叉树的中序遍历。第三行是这个二叉树的后序遍历。输入输出样例输入 #17 2 7 4 0 0 0 0 3 0 0 0 5 6 0输出 #11 2 4 3 7 6 5 4 3 2 1 6 5 7 3 4 2 5 6 7 1题目分析这道题根据树的遍历可以分成三部分为前序遍历中序遍历后序遍历。遍历详情见有关树的存储与二叉树的遍历-CSDN博客前序遍历为根左右。先输出自己再输出左然后返回到右而中序遍历则为判断自己的左节点是否遍历过了或是否为空等自己左节点为空或被遍历后输出自己然后再看右节点。最后后序遍历用while循环根节点的左与右节点都被遍历后或都为0时则结束否则执行while循环如果自己的左与右节点都输出过或为空则输出自己标记自己。代码#includebits/stdc.h using namespace std; const int maxn1e65; vectorint t[maxn]; bool p[maxn];//中序遍历的标记数组 bool st[maxn];//后序遍历的标记数组 int x1[maxn]; void dfs(int m) { if(m!0) coutm ; for(int i0; it[m].size(); i) { dfs(t[m][i]); } } void z(int m) { if(p[t[m][0]]false) { coutm ; p[m]false; if(p[t[m][1]]!false) { z(t[m][1]); } return; } for(int i0; it[m].size(); i) { if(i0) { if(p[t[m][i]]!false) { z(t[m][i]); } } if(p[m]!false){ coutm ; p[m]false; } if(i1){ if(p[t[m][i]]!false) { z(t[m][i]); } } } } int main() { int n; cinn; for(int i1; in; i) { st[i]true; p[i]true; } for(int i1; in; i) { int l,r; cinlr; t[i].push_back(l); t[i].push_back(r); } dfs(1);//前序遍历 coutendl; z(1);//中序遍历 coutendl; int j0; int x1; x1[j]x; while(st[t[1][0]]!false||st[t[1][1]]!false) { if(st[t[x][0]]falsest[t[x][1]]false) { coutx ; st[x]false; while((st[t[x][0]]falsest[t[x][1]]false)x!1) { xx1[--j];//返回 } } else { for(int i0; it[x].size(); i) { if(st[t[x][i]]!false) { xt[x][i]; x1[j]x; break; } } } }//后序遍历 cout1;//输出根节点 return 0; }
