⼆叉树的遍历【NOIP2001普及组】洛⾕P1030求先序排列
题⽬链接
模板题
先讲⼀下⼆叉树的遍历
⼆叉树的遍历
分类
性质
求法
分为三类：
1. 先序遍历(PreOrder)：根节点→左⼦树→右⼦树
2. 中序遍历(InOrder)：左⼦树→根节点→右⼦树
3. 后序遍历(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
求后序遍历
⽤到递归的思想，求整个⼆叉树的后序遍历就是求每个⼦树的后序遍历，最后连接起来即可。
1 #include<iostream>
2using namespace std;
3string z,q;
4int len,cnt;
5void PostOrder(int l,int r){//求中序遍历中l到r这个⼦树的后序遍历
6if(l>r) return; //边界条件
7int i;
8char ans=q[cnt++]; //先序遍历的第⼀个是根节点
9for(i=l;i<=r;i++){
10if(z[i]==ans) break;//到根节点在中序遍历中的位置
11 }
12 PostOrder(l,i-1); //递归左⼦树
13 PostOrder(i+1,r); //递归右⼦树
14 cout<<ans; //注意后序遍历是左右根的顺序，所以最后输出根
15 }
16int main()
17 {
18 cin>>z>>q; //z是中序遍历，q是先序遍历
19 len=z.length()-1;
20 PostOrder(0,z.length()-1);//⼀开始是整个⼦树
21return0;
22 }
求先序遍历
这⽐求后序遍历稍微有些复杂，需要保留根节点，即：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……显然是按照根→右⼦树→左⼦树排列的，⽽我们求的先序排列是根→左→右，显然这种⽅法不⾏。
所以我们需要多传⼀个参数，来记录根节点在后序遍历中的位置。重点：确定⼦树的根节点在后序遍历中的位置。
1 #include<iostream>
2using namespace std;
3string z,h;
4int len;
5void PreOrder(int l,int r,int root){//求中序遍历中l到r这个⼦树(以root为根)的后序遍历
6if(l>r) return;
7int i;
8for(i=l;i<=r;i++){ //和求后序遍历⼀样
9if(z[i]==h[root]) break;
10 }
11 cout<<h[root]; //注意是根左右
12 PreOrder(l,i-1,root-(r-i)-1);//左⼦树的根节点就是原来根节点减去右⼦树的节点数的上⼀个(r-i就是右⼦树的节点数)
13 PreOrder(i+1,r,root-1); //右⼦树的根节点就是后序遍历中原来根节点的上⼀个
14 }
15int main()
16 {
17 cin>>z>>h;
18 len=h.length()-1;
19 PreOrder(0,z.length()-1,len);
20return0;
21 }
⽽在知道先序遍历和后序遍历的情况下，中序遍历是不唯⼀的，但可以求出情况数(后⾯将做补充)。
//NOIP2001普及组t3
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论