5.3.1.5 由遍历序列构造二叉树

教材导航 · 第5章

原书定位

印刷页P143起,对应PDF第155页。下文为目视整理的知识提要;完整内容见原书对照。

在结点标识互不相同的前提下,中序加先序、后序或层序,可唯一确定二叉树。

  • 先序首项、后序末项分别给出根;根在中序中的位置将左右子树分开,按元素数切分另一个序列并递归。
  • 层序的首项给根,按中序左右集合筛分后续层序,再递归处理。
  • 单一遍历序列一般不够;先序加后序也一般不能区分单孩子结点的左右位置。重复标识或额外结构约束需要另作判断。

图5.11 由先序和中序划分子树

图5.11 由先序和中序划分子树,原书P143。

图5.12 二叉树构造过程

图5.12 二叉树构造过程,原书P144。

图5.13 由后序和中序划分子树

图5.13 由后序和中序划分子树,原书P144。

图5.14 由层序和中序划分子树

图5.14 由层序和中序划分子树,原书P144。

图5.15 遍历序列相同而形态不同的两棵树

图5.15 遍历序列相同而形态不同的两棵树,原书P145。

对应练习

5.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P143,PDF第155页

原书对照,原书P144,PDF第156页

原书对照,原书P145,PDF第157页