树的遍历总结

一.树的遍历方式

树的遍历方式按节点数据访问位置分为前序遍历，中序遍历和后序遍历。 首先就是，访问左子树和右子树的顺序是一样的，总是 访问左子树->访问右子树，这样很明显，访问当前根节点数据的程序有三个位置可以放，分别是： 访问根->访问左子树->访问右子树（前序遍历）； 访问左子树->访问根->访问右子树（中序遍历）； 访问左子树->访问右子树->访问根（后序遍历）； 0.树的定义

struct node { int num; node *l; node *r; };

1.前序遍历代码

void print_front(node *root) { printf("%d ",root->num); print_front(root->l); print_front(root->r); }

2.中序遍历代码

void print_mid(node *root) { print_front(root->l); printf("%d ",root->num); print_front(root->r); }

3.后序遍历代码

void print_back(node *root) { print_front(root->l); print_front(root->r); printf("%d ",root->num); }

4.树的层序遍历 顾名思义，就是一层一层的从左到右输出节点数据，这样可以用bfs来做

void bfs(int x) { queue<int> q; vector<int> v; q.push(x); while(!q.empty()) { int temp=q.front(); q.pop(); if(temp==0) break; v.push_back(temp); if(tree[temp].l!=0) q.push(tree[temp].l); if(tree[temp].r!=0) q.push(tree[temp].r); } int len=v.size(); for(int i=0;i<len;i++) { printf("%d",v[i]); if (i==len-1) printf ("\n"); else printf (" "); } return ; }

二.根据前序结果/后序结果+中序结果来读取树

题目

题目传送门

#include<iostream> #include<cstdlib> #include<queue> #include<vector> using namespace std; struct node { int l; int r; }; node tree[100]; int a[100]; int b[100]; int build(int la,int ra,int lb,int rb)//a是后序 b是中序 { if(la>ra) return 0; int rt=a[ra]; int i; for(i=lb;i<=rb;i++) if(b[i]==rt) break; tree[rt].l=build(la,la+i-lb-1,lb,i-1); tree[rt].r=build(la+i-lb,ra-1,i+1,rb); return rt; } void bfs(int x) { queue<int> q; vector<int> v; q.push(x); while(!q.empty()) { int temp=q.front(); q.pop(); if(temp==0) break; v.push_back(temp); if(tree[temp].l!=0) q.push(tree[temp].l); if(tree[temp].r!=0) q.push(tree[temp].r); } int len=v.size(); for(int i=0;i<len;i++) { printf("%d",v[i]); if (i==len-1) printf ("\n"); else printf (" "); } return ; } int main() { int n; cin>>n; for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n;i++) scanf("%d",&b[i]); build(0,n-1,0,n-1); bfs(a[n-1]); return 0; }