L2-006 树的遍历

详细注释，兄弟们，冲!

受益匪浅：

1：图（树）的构建：（根据中序，和后序）（中序，和后序原理都一样）

int build_tree(int l1,int r1,int l2,int r2){//构建树 if(l1>r1||l2>r2){//结束 return 0;}int root=last[r2];//当前根节点int p=l1;//从mid中找while(mid[p]!=root)p++;//知道找到root(当前根节点的位置)int cnt=p-l1;t[root].l=build_tree(l1, p-1,l2,l2+cnt-1);//构建左子树 t[root].r=build_tree(p+1,r1,l2+cnt,r2-1); //构建右子树 return root;//返回根节点 
}

2：如何进行层序遍历：

void dfs(int root){//层序遍历 queue<int>q;//用到队列 q.push(root);//第一个根根节点入队 int flag=true;while(q.size()){int tt=q.front();q.pop();if(flag){//最后不能有多余空格，这样操作很巧妙，爱了爱了 cout<<tt;flag=false;}else{cout<<" "<<tt;}if(t[tt].l)q.push(t[tt].l);//一层一层直接入队，一层先入队就先打印，层序遍历 if(t[tt].r)q.push(t[tt].r);}return;
}

3：（处理输出末行不能多出空格的情况） 

(第一个数只输出本身，后来都是先输出一个空格再输出本身)

int flag=true;if(flag){//最后不能有多余空格，这样操作很巧妙，爱了爱了 cout<<tt;flag=false;}else{cout<<" "<<tt;}

 最后是ACcode:(详细注释，安全食用~)

#include<iostream>
#include<queue>
using namespace std;
const int N =30+5;
struct T{//构建树 int l,r;
}t[N];int mid[N],last[N],n;//中序，后序，n 
int build_tree(int l1,int r1,int l2,int r2){//构建树 if(l1>r1||l2>r2){//结束 return 0;}int root=last[r2];//当前根节点int p=l1;//从mid中找while(mid[p]!=root)p++;//知道找到root(当前根节点的位置)int cnt=p-l1;t[root].l=build_tree(l1, p-1,l2,l2+cnt-1);//构建左子树 t[root].r=build_tree(p+1,r1,l2+cnt,r2-1); //构建右子树 return root;//返回根节点 
}
void dfs(int root){//层序遍历 queue<int>q;//用到队列 q.push(root);//第一个根根节点入队 int flag=true;while(q.size()){int tt=q.front();q.pop();if(flag){//最后不能有多余空格，这样操作很巧妙，爱了爱了 cout<<tt;flag=false;}else{cout<<" "<<tt;}if(t[tt].l)q.push(t[tt].l);//一层一层直接入队，一层先入队就先打印，层序遍历 if(t[tt].r)q.push(t[tt].r);}return;
}
int main() {cin>>n;for(int i=1;i<=n;i++){cin>>last[i];}for(int i=1;i<=n;i++){cin>>mid[i];}int root=build_tree(1,n,1,n);//构建树 dfs(root); //层序遍历打印 return 0;
}

over~,点赞点赞