答案解析:考查...
参考答案:A
答案解析:考查树的遍历、及由遍历序列确定二叉树的树形。
前序序列和后序序列不能唯一确定一棵二叉树,但可以确定二叉树中结点的祖先关系:当两个结点 的前序序列为 XY 与后序序列为 YX 时,则 X 为 Y 的祖先。考虑前序序列 a,e,b,d,c、后序序列 b,c,d,e,a, 可知 a 为根结点,e 为 a 的孩子结点;此外,a 的孩子结点的前序序列 e,b,d,c、后序序列 b,c,d,e,可知 e 是 bcd 的祖先,故根结点的孩子结点只有 e。本题答案为 A。
已知某二叉树的前序遍历序列和后序遍历序列,能构造的二叉树不一定唯一。
前序遍历是“根左右”遍历,后序遍历是“左右根”遍历。
第一轮递归:从前序遍历序列中取出第一个元素作为二叉树的根结点,从后序遍历序列中取出最后一个元素作为二叉树的根结点,这两个元素一定相同,否则无法构造二叉树,本题均为a。
第二轮递归:从前序遍历序列未处理的子串中取出第一个元素作为二叉树的左子树的根结点,从后序遍历序列未处理的子串中取出最后一个元素作为二叉树的右子树的根结点,这两个元素不一定相同。如果相同,说明有一个子树为空,本题均为e,也就是根结点只有一个孩子结点e,e可以随机分配在左子树或者右子树。
到这里没必要继续递归执行了,本题只要求出根结点的孩子结点即可。
本题选A。
登录后提交答案
暂无评论,来抢沙发