2. 从业资格
  3. 已知某二叉树的先序遍历序列是 ABDCE，中序遍历序列是 BDAEC，则该二叉树

已知某二叉树的先序遍历序列是 ABDCE，中序遍历序列是 BDAEC，则该二叉树

admin2022-08-02  72
问题 已知某二叉树的先序遍历序列是 ABDCE，中序遍历序列是 BDAEC，则该二叉树为（  ）。
选项
答案 C
解析 本题考查数据结构基础知识对二叉树进行先序遍历的过程是：若二叉树非空，则先访问根结点，然后先序遍历左子树，最后先序遍历右子树。因此，在二叉树的先序遍历序列中，第一个元素是根结点。对二叉树进行中序遍历的过程是：若二叉树非空，则首先中序遍历左子树，然后访问根结点，最后中序遍历右子树。因此，若在中序遍历序列中已找出二叉树的根结点，则根结点左边为左子树的中序遍历序列，右边是右子树的中序遍历序列。由此，根据先序序列确定根结点，根据中序序列划分左、右子树，反复应用此原则，就可根据先序遍历序列和中序遍历序列恢复二叉树的结构。本题中，先序序列为ABDCE，因此A是树根结点，中序序列为BDAEC，因此BD是左子树上的结点，EC是右子树上的结点。接下来根据先序遍历序列，可知B是左子树的根结点，C是右子树的根结点。在中序遍历序列BDAEC中，D在B之后，因此D是B的右孩子。同理，在中序遍历序列BDAEC中，E在C之前，因此E是C的左孩子。即该二叉树如下图所示。
转载请注明原文地址:https://tihaiku.com/congyezige/2428571.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

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