流离之人追逐幻影

用户名：pwj666

访问量：60250

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13962
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：188

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

二叉树遍历-题解(C++代码)

　　作者: 流离之人追逐幻影　　　　发表时间：2019-10-20 22:07:19 浏览：944　|　评论：0　

原题链接：二叉树遍历

PS:大三了，High了两年，差不多要准备考研了，先复习一下数据结构里面的二叉树，减轻一下后面复习的压力。come on!

------------
首先要做这道题，必须先理解数据结构 二叉树多种遍历原理，已经忘记了的同志可以点击下述链接。
预备知识：[【数据结构】遍历二叉树](https://zhuanlan.zhihu.com/p/38603548 "【数据结构】遍历二叉树")

![](/image_editor_upload/20191020071432_44224.png)

前序遍历：ABDECFG
中序遍历：DBEAFCG
后序遍历：DEBFGCA

现在，假设仅仅知道前序和中序遍历，如何求后序遍历呢？
```
第一步：前序遍历的第一节点A就是root

第二步：观察中序遍历 知，A左边的DBE 是A的左子树，A右边的FCG 是A的右子树

第三步：由第二步知，A的左右子树有各有3节点，观察前序遍历 知，B是左子树的root，C是右子树的root

第四步：观察中序遍历 知，B的左边D 是B的左子树，B的右边E 是B的右子树，
所有字母观察完毕，画出这个树的图，然后就可以写这个树的后序遍历了。
```
理解上面的意思后就可以确定代码框架了：
```
	首先在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的右子树的第一个节点就是右子树的根节点。
	
1 利用前序遍历和中序遍历确定根在中序遍历的位置,

2 在（中序遍历）左子树中递归。

3 在 (中序遍历) 右子树中递归。

4 打印当前根。
```

巧记：前序遍历根左右，中序遍历左根右，后续遍历左右根

------------

AC代码：
```
#include <cstdio>
#include<cstring>
using namespace std;

void LastSearchOrder(char *pr,char *in,int length) {
    if(!length) return ;
    int RootPos = 0;
    for(;RootPos<length;RootPos++) {
        if(in[RootPos] == *pr) break;
    }
    LastSearchOrder(pr+1,in,RootPos);
    LastSearchOrder(pr+1+RootPos,in+1+RootPos,length-RootPos-1);
    printf("%c",*pr);
}
char pr[10005], in[10005];
int main()
{
   
    while(scanf("%s",pr)!=EOF){ 
    scanf("%s",in);
    LastSearchOrder(pr,in,strlen(pr));
    printf("\n");
}
    return 0;
}
```
为了更深刻的理解上面的递归：
所以我手动模拟了上面的递归过程：
```
前序遍历：ABDECFG
中序遍历：DBEAFCG
第一步：初始
length=7  
进入递归

第二步：
length=7
 ABDECFG
 ^
 DBEAFCG
    ^
RootPos = 3   进入左子树（中序）

第三步：
length=3
 ABDECFG
  ^
 DBEAFCG
  ^
RootPos = 1   进入左子树（中序）

第四步：
length=1
 ABDECFG
   ^
 DBEAFCG
 ^
RootPos = 0  进入左子树（中序）

第五步：
length=0  
回退到第四步
length=1  RootPos = 0  进入右子树（中序）
length=0  
回退到第四步
打印D
回退到第三步
......之后同理了，模拟到手有点酸---TT,
【后序遍历：DEBFGCA】
```

举一反三：
如果给出中序遍历和后序遍历，怎么求前序遍历？
如果给出前序遍历和后序遍历，怎么求中序遍历？

PS：
```
19/10/21 
刚复习的时候发现，前序与中序 和 中序和后序能够还原成唯一的二叉树,说明他们包含的信息已经足以覆盖这棵二叉树的全部信息,而前序和后序有的却不能唯一确认一颗二叉树，这一点其实也比较好理解，有线性代数基础的同学肯定会熟悉这样一种现象，即列向量a与列向量b线性无关（即a、b之间无法通过线性变换互相表示），向量b与向量c线性无关，但是我们不能说明a与c也是线性无关的，他们之间不满足传递性。在a与c线性相关的情况下，a与c虽然并不相同，但是他们携带的信息却有很多重复。这样就造成了对于a、b、c三个不同的向量，其实他们所携带的信息只需要a、b两个向量以及一个其他的小于c所携带的信息的“量”就可以了，那个“量”也就是a、c之间不重复的部分。
```
参考文章：[为什么只给出前序和后序，不能唯一确定一个二叉树](https://blog.csdn.net/yusiguyuan/article/details/42687623 "为什么只给出前序和后序，不能唯一确定一个二叉树")

------------

0.0分

8 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C二级辅导-同因查找（C++代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

拆分位数（C++代码）用char简单粗暴，嗯

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

二叉树遍历-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

钟神赛车（C++代码）

C语言训练-求函数值（C语言代码）

【出圈】（C语言代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C二级辅导-同因查找 （C++代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

拆分位数 （C++代码）用char简单粗暴，嗯

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

二叉树遍历-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

钟神赛车 （C++代码）

C语言训练-求函数值 （C语言代码）

【出圈】 （C语言代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C二级辅导-同因查找（C++代码）

拆分位数（C++代码）用char简单粗暴，嗯

　　评论区

钟神赛车（C++代码）

C语言训练-求函数值（C语言代码）

【出圈】（C语言代码）

母牛的故事（C语言代码）