反向构造二叉树

未匹配的标注

@author 汪春波

条件1 .由前序序列为 ABHFDECG 根左右

条件2. 中序序列为 HBED F A GC 左根右

ps 必须有中序序列才可以推出二叉树

第一步

有条件1 知道。根为 A
条件2 知道,左边第一个为 H 。 那么得到了根为A,所以,树的左右为, HBED GC

反向构造二叉树

第二步

那么 我们来看 HBEDF
条件2 知道 左 根 右,推出 B肯定为根节点。按照位置即可推出。
条件1 知道 根左右。 则 B 肯定为左边的。
所以第二层第一个为 B

根据 HBEDF 推出(中序给出结果 左根右边
B 的子节点为,左边肯定为 H,右边为 EDF

反向构造二叉树

第三

由中序,
则 EDF为

D根 ,推测,D 左右为 E F

反向构造二叉树

由 前序,FDE 根左右
得到,F 也为根。


反向构造二叉树

结合发现冲突,则排序一下,
D 下面 肯定是 E
F 下面肯定是 D
所以得到

反向构造二叉树

第四 右边

GC

根据 中序,得到 C定为根,G左。

根据前序得到, C定为根,G左。

所以

反向构造二叉树

结果拼起来

反向构造二叉树

本文章首发在 LearnKu.com 网站上。

上一篇 下一篇
讨论数量: 0
发起讨论 只看当前版本


暂无话题~