题41
题目
【2017 统考真题】要使一棵非空二又树的先序序列与中序序列相同, 其所有非叶结点须满足的条件是 ( ).
A. 只有左子树
B. 只有右子树
C. 结点的度均为 1
D. 结点的度均为 2
分析
先序是根左右
中序是左根右
同时划掉左，剩下根和右，也就是右子树
解
B
先序序列先访问父结点, 接着访问左子树, 然后访问右子树。
中序序列先访问左子树, 接着访问父结点, 然后访问右子树, 递归进行。若所有非叶结点只有右子树, 则先序序列和中序序列都先访问父结点, 后访问右子树, 递归进行。