若将一棵树T转化为对应的二又树BT,则下列对BT的遍历中,其遍历序列与T的后根遍历序列相同的是
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
没人了?
解答:
将一棵树T转化为对应...
用户登录可进行刷题及查看答案
将一棵树T转化为对应的二叉树BT,用的是“左孩子右兄弟”规则,即每个结点的左指针指向它的第一个孩子,右指针指向它在树中相邻的右兄弟。
方法一:推理
树T的后序遍历是先孩子后根,是一个自底向上的遍历顺序,对应二叉树BT中的一个从左到右的遍历顺序,即中序遍历。如果不能理解中序遍历是从左到右的,将二叉树中所有结点都向下进行投影,投影得到的序列就是中序遍历序列。
本题选B。
方法二:画图举例
当然方法一比较抽象,比较难想。我们可以直接画出一棵树,写出其后根遍历序列,将他转化为二叉树,观察这个后根遍历序列与二叉树的哪个遍历序列一致。
但是这个举例又非常有讲究,要具有区分度又不能太复杂,我们先尝试构造出一棵高度为2的满三叉树。
很明显,这里BT的中序遍历序列与T的后根遍历序列相同。
登录后提交答案