题目链接
https://www.luogu.org/problemnew/show/P1030
模板题
先讲一下二叉树的遍历
二叉树的遍历
- 分类
- 性质
- 求法
分为三类:
- 先序遍历(PreOrder):根节点→左子树→右子树
- 中序遍历(InOrder):左子树→根节点→右子树
- 后序遍历(PostOrder):左子树→右子树→根节点
我们可知:
- **序遍历实际上是指根节点的位置
- 无论哪种遍历顺序,左子树都在右子树的前面
- 在前序遍历中,第一个点是根节点
- 在后序遍历中,最后一个点是根节点
例如这样一个二叉树:
它的先序遍历:A--B--D--E--X--C--F--Y--Z
它的中序遍历:D--B--X--E--A--Y--F--Z--C
它的后序遍历:D--X--E--B--Y--Z--F--C--A
求后序遍历
用到递归的思想,求整个二叉树的后序遍历就是求每个子树的后序遍历,最后连接起来即可。
#include<iostream>
using namespace std;
string z,q;
int len,cnt;
void PostOrder(int l,int r){//求中序遍历中l到r这个子树的后序遍历
if(l>r) return; //边界条件
int i;
char ans=q[cnt++]; //先序遍历的第一个是根节点
for(i=l;i<=r;i++){
if(z[i]==ans) break;//找到根节点在中序遍历中的位置
}
PostOrder(l,i-); //递归左子树
PostOrder(i+,r); //递归右子树
cout<<ans; //注意后序遍历是左右根的顺序,所以最后输出根
}
int main()
{
cin>>z>>q; //z是中序遍历,q是先序遍历
len=z.length()-;
PostOrder(,z.length()-);//一开始是整个子树
return ;
}
求先序遍历
这比求后序遍历稍微有些复杂,需要保留根节点,即:PreOrder(左端点,右端点,根节点)。这是因为根节点在先序遍历中是从前往后排列的,而在后序遍历中不是这样的。
还是这个图:
它的先序遍历:A--B--D--E--X--C--F--Y--Z
它的中序遍历:D--B--X--E--A--Y--F--Z--C
它的后序遍历:D--X--E--B--Y--Z--F--C--A
在先序遍历中,根节点依次是A,B,D,E,X……是按照从前往后的顺序排列的,所以可以直接 ans=q[cnt++]; 而在后序遍历中却不是这样。
有人或许会说:那后序遍历中根节点是从后往前排列的,其实这是一个错误的结论。还是看这一个二叉树,后序遍历是A,C,F,Z,Y,B……显然是按照根→右子树→左子树排列的,而我们求的先序排列是根→左→右,显然这种方法不行。
所以我们需要多传一个参数,来记录根节点在后序遍历中的位置。重点:确定子树的根节点在后序遍历中的位置。
#include<iostream>
using namespace std;
string z,h;
int len;
void PreOrder(int l,int r,int root){//求中序遍历中l到r这个子树(以root为根)的后序遍历
if(l>r) return;
int i;
for(i=l;i<=r;i++){ //和求后序遍历一样
if(z[i]==h[root]) break;
}
cout<<h[root]; //注意是根左右
PreOrder(l,i-,root-(r-i)-);//左子树的根节点就是原来根节点减去右子树的节点数的上一个(r-i就是右子树的节点数)
PreOrder(i+,r,root-); //右子树的根节点就是后序遍历中原来根节点的上一个
}
int main()
{
cin>>z>>h;
len=h.length()-;
PreOrder(,z.length()-,len);
return ;
}
而在知道先序遍历和后序遍历的情况下,中序遍历是不唯一的,但可以求出情况数(后面将做补充)。
//NOIP2001普及组t3