⼆叉树的前序、中序和后序遍历
今天做到阿⾥巴巴的⼀道笔试题，关于⼆叉树的遍历序列的，原题摘录如下：
某⼆叉树的先序遍历是12453，中序遍历是42513，那么其后续遍历是？
A 45231
B 42351
C 12345
D 54321
本题答案为A
本题考查的知识点是⼆叉树前序、中序、后序遍历的相互求法，即如果知道两个的遍历，如何求第三种遍历。
⾸先，我们看看前序、中序、后序遍历的特性：
1. 前序遍历（前序遍历）：
1.访问根节点
2.前序遍历左⼦树
3.前序遍历右⼦树
2. 中序遍历：先序中序后序遍历二叉树
1.中序遍历左⼦树
2.访问根节点
3.中序遍历右⼦树
3. 后序遍历：
1.后序遍历左⼦树
2.后序遍历右⼦树
3.访问根节点
以本题为例简单说明：先序遍历是 12453 依据先序遍历的特性：先序是先访问根节点 所以1是⼆叉树的根节点，后序遍历是先访问左⼦树和右⼦树，后访问 425**1**3，在1的左边的是⼆叉树的左⼦树425,1右边的3是⼆叉树的右⼦树，右⼦树只有⼀个节点，所以可以先构造出⼀个⼆叉树为
1
3(1的右⼦树)
再看先序遍历 1 245 3和后序遍历**425***1*3，2是左⼦树的根节点，在后序遍历中 2在4和5的中间 ，所以 4是2的左⼦树，5是2的右⼦树，构造出的⼆叉树为：
1
21的左⼦树) 3（1的右⼦树)
4 （2的左⼦树) 5（2的右⼦树)
所以后序遍历序列为 45231
本题答案为A
如果给出后序遍历和中序遍历来求前序遍历的分析也是⼀样。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。