二叉树的遍历 &【NOIP2001普及组】& 洛谷 P1030 求先序排列

题目链接

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

二叉树的遍历 &【NOIP2001普及组】& 洛谷 P1030 求先序排列的相关教程结束。