5.3.1.5 由遍历序列构造二叉树
原书定位
印刷页P143起,对应PDF第155页。下文为目视整理的知识提要;完整内容见原书对照。
在结点标识互不相同的前提下,中序加先序、后序或层序,可唯一确定二叉树。
- 先序首项、后序末项分别给出根;根在中序中的位置将左右子树分开,按元素数切分另一个序列并递归。
- 层序的首项给根,按中序左右集合筛分后续层序,再递归处理。
- 单一遍历序列一般不够;先序加后序也一般不能区分单孩子结点的左右位置。重复标识或额外结构约束需要另作判断。

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

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

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

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

图5.15 遍历序列相同而形态不同的两棵树,原书P145。
对应练习
关联知识
原书对照
展开原书对照截图


