二叉树遍历

1.广度优先遍历

2.深度优先遍历

1.前序遍历

根结点--左子树--右子树

void pre(int p){printf("%d\n",p);if(tree[p].l)pre(tree[p].l);if(tree[p].r)pre(tree[p].r);
}

2.中序遍历

左子树--根结点--右子树

void in(int p){if(tree[p].l)in(tree[p].l);printf("%d\n",p);if(tree[p].r)in(tree[p].r);
}

3.后序遍历

左子树--右子树--根结点

void post(int p){if(tree[p].l)post(tree[p].l);if(tree[p].r)post(tree[p].r);printf("%d\n",p);
}

3.已知先中求后

P1827 [USACO3.4] 美国血统 American Heritage

#include<bits/stdc++.h>
using namespace std;
string a,b;
void dfs(int l,int r,int ql,int qr){for(int i=ql;i<=qr;i++){if(a[i]==b[l]){dfs(l+1,l+i-ql,ql,i-1);  //i-ql表示左子树长度dfs(l+i-ql+1,r,i+1,qr);cout<<b[l];}}
}
int main(){cin>>a>>b;dfs(0,a.length()-1,0,a.length()-1);return 0;
}

4.已知中后求先

P1030 [NOIP 2001 普及组] 求先序排列

反过来即可

#include<bits/stdc++.h>
using namespace std;
string a,b;
void dfs(int l,int r,int ql,int qr){for(int i=qr;i>=ql;i--){if(a[i]==b[r]){cout<<b[r];dfs(l,r-(qr-i)-1,ql,i-1);  dfs(r+i-qr,r-1,i+1,qr);}}
}
int main(){cin>>a>>b;dfs(0,a.length()-1,0,a.length()-1);return 0;
}

5.已知先后求中的可能个数

P1229 遍历问题

有n个只有一个子树的结点就有2^n种可能

输入例子：

前：abc

后：cba

若两个字母在前序与后序中位置相邻且相反，那便是一个单子树结点

因为前序是根左右

后序是左右根

若存在两个子树

那么相邻一定不一样

#include<bits/stdc++.h>
using namespace std;
string a,b; 
long long ans;
int main(){cin>>a>>b;int n=a.length();for(int i=0;i<=n-2;i++){for(int j=0;j<=n-1;j++){if(a[i]==b[j]&&a[i+1]==b[j-1])ans++;}}cout<<pow(2,ans);return 0;
}