2. 从业资格
  3. 若某二叉树的后序遍历序列为KBFDCAE，中序遍历序列为BKEFACD，则该二叉

若某二叉树的后序遍历序列为KBFDCAE，中序遍历序列为BKEFACD，则该二叉

免费题库2022-08-02  23
问题 若某二叉树的后序遍历序列为KBFDCAE，中序遍历序列为BKEFACD，则该二叉树为（　　）。
选项
答案 A
解析 本题考查二叉树的遍历。
二叉树的主要遍历方式有：前序遍历、中序遍历、后序遍历、层次遍历。如果已知中序遍历，并知道前序遍历与后序遍历中的任意一个，便可得到一棵唯一的二叉树。
具体是怎么做的呢？
利用的是遍历的特点。中序遍历的顺序是：左、根、右。而后序遍历的顺序是：左、右、根。
回到题目里面来，从“后序遍历序列为KBFDCAE”，可以得知，二叉树的根结点为：E（此时已经可以排除选项C与选项D了）。继续分析，由“中序遍历序列为BKEFACD”，可以得知，二叉树的左子树包括结点：BK。右子树包括结点：FACD。
重复上面的步骤，对左子树与左子树看成独立的两棵树进行分析。在后序遍历中，左子树的结点BK的顺序为“KB”，所以B是根结点；右子树的结点FACD的顺序为“FDCA”，所以右子树的根结点为A。当分析到这一步时，已经可以得到本题答案为A。
转载请注明原文地址:https://tihaiku.com/congyezige/2409937.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)