题10

题10

题目

Q:若 是由有序树 转换而来的二叉树,则 中结点的后根序列就是 中结点的 （ ） 序列.
A. 先序
B. 中序
C. 后序
D. 层序

分析

A:普通树转成二叉树，遵循的是
兄弟连起来，留下左子线



也就是原本的兄弟变成了右孩子
T1是二叉树的中序，中序是左根右
T是原树，后序是左右根
兄弟也就是

解

B
有序树 转换成二叉树 时, 的后根序列是对应 的中序序列还是后序序列呢 (显然树的后根序列不可能对应二叉树的先序序列和层序序列) ?
看下图所示的例子,在树 中,叶结点 应最先访问,在 中, 的右兄弟 转换为它的右孩子,若对应 的后序序列,则 应在 的前面访问,所以 的后根序列不可能对应 的后序序列。