已知⼆叉树的先序遍历序列和中序遍历序列，求其后序遍历序列2018.1.19 Fri
已知⼆叉树的先序遍历序列和中序遍历序列，求其后序遍历序列
例：
先序遍历：ABDGCEFH
中序遍历：DGBAECHF
解：
⾸先要先知道各种遍历⽅式的规则：
先序遍历（先根遍历、前序遍历）：1. 访问根结点2. 遍历左⼦树3. 遍历右⼦树
中序遍历（中根遍历）：1. 遍历左⼦树2. 访问根结点3. 遍历右⼦树
后序遍历（后根遍历）：1. 遍历左⼦树2. 遍历右⼦树3. 访问根结点
且⽆论哪种遍历，左右⼦树仍然遵循该遍历规则。若没有左⼦结点或右⼦结点（即不是满⼆叉树，如图2）则输出⼀个空代替⼀下就好，然后继续遍历。例如图⼆中后序遍历为：BOA，即BA。
因为先序遍历是先访问根节点，所以A⼀定是根节点。因此可以进⾏如下拆分：
先序遍历：A  BDGCEFH
中序遍历：DGB  A  ECHF
⼜因为中序遍历的顺序是：左⼦树，根节点，右⼦树，所以再拆
  先序遍历：A  BDG  CEFH
中序遍历：DGB  A  ECHF
然后同理看BDG树
先序遍历：B  DG
中序遍历：DG  B
得到B是A的左⼦结点。
同理看DG树：
  先序遍历：D  G
中序遍历：D  G
得到D是B的左⼦结点， G是D的右⼦结点。（因为如果G是左⼦结点的话中序遍历是GD）。
得到了左⼦树。
右⼦树同理：
先序遍历：C  E  FH
  中序遍历：E  C  HF
得到C是A的右⼦结点，E是C的左⼦结点。
先序遍历：F  H
  中序遍历：H  F
得到F是C的右⼦结点，H是F的左⼦结点。得到右⼦树。
得到如图1的⼆叉树。
二叉树前序中序后序图解
然后得到后序遍历：
GDBEHFCA

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