校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 二叉树遍历
题目

如何根据先序中序求后序。

A. 1)先序序列最中间一个元素为根结点,将线性表分为两部分(即二叉树的左右子树),再用中序去分别处理两个部分(即判断左右)。2)对每个部分再执行1),直到剩余一个结点。

B. 1)中序序列第一个元素为根结点,将线性表分为两部分(即二叉树的左右子树),再用先序去分别处理两个部分(即判断左右)。2)对每个部分再执行1),直到剩余一个结点。

C. 1)先序序列第一个元素为根结点,将线性表分为两部分(即二叉树的左右子树),再用中序去分别处理两个部分(即判断左右)。2)对每个部分再执行1),直到剩余一个结点。

D. 不能求出

解答

正确答案:C

先序序列就是对一棵二叉树进行先序遍历得到的一串序列。先序遍历就是:首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树,如果二叉树为空则返回。

中序序列就是对一棵二叉树进行中序遍历得到的一串序列。中序遍历就是:中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。在遍历左、右子树时,仍然先遍历左子树,再访问根结点,最后遍历右子树。

后序序列就是对一棵二叉树进行后序遍历得到的一串序列。后序遍历就是:后序遍历首先遍历左子树,然后遍历右子树,最后遍历访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。

按如下步骤求解
1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。
2、求解树的子树。找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树。若根节点左边或右边为空,则该方向子树为空;若根节点左边和右边都为空,则根节点已经为叶子节点。
3、递归求解树。将左子树和右子树分别看成一棵二叉树,重复1、2、3步,直到所有的节点完成定位。

C 1条回复 评论
你是闰土我是猹

这套课质量挺值得价格的

发表于 2021-09-08 20:05:00
0 0