若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1,则该二又树的中序遍历序列不会是____。

admin2013-04-26  26

问题 若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1,则该二又树的中序遍历序列不会是____。

选项 A、1,2,3,4
B、2,3,4,1
C、3,2,4,1
D、4,3,2,1

答案C

解析 考查二叉树的遍历算法。前序序列为LRN,后序序列为NLR,由于前序序列和后序序列刚好相反,故不可能存在一个结点同时存在左右孩子,即二又树的高度为4.1为根结点,由于根结点只能有左孩子(或右孩子),因此,在中序序列中,1或在序列首或在序列尾,ABCD皆满足要求。仅考虑以l的孩子结点2为根结点的子树,它也只能有左孩子(或右孩子),因此,在中序序列中,2或在序列首或序列尾,ABD皆满足要求。
转载请注明原文地址:https://kaotiyun.com/show/Hwxi777K
0

最新回复(0)