首页 > 试题广场 >

某二叉树结点的中序序列为A、B、C、D、E、F、G，后续序列

[单选题]
某二叉树结点的中序序列为A、B、C、D、E、F、G，后续序列为B、D、C、A、F、G、E。该二叉树对应的树林包括多少棵树： 
  • 1
  • 2
  • 3
  • 4
添加回答
推荐
牛客444334号头像 牛客444334号
B 

第一步：还是先求root根节点，根据后序遍历规则我们可知root为后序遍历序列的最后一个节点，因此该二叉树的root节点为E。

  第二步：求root的左子树和右子树，这点我们还是从中序遍历序列中找出，位于root节点E左侧的ABCD为root的左子树，位于E右侧的FG为右子树。

  第三步：求root的左孩子leftchild和右孩子rightchild，leftchild为左子树的根节点，rightchild为右子树的根节点。我们可以找到左子树ABCD在后序遍历序列中的排列顺序为BDCA，由于后序遍历最后访问根节点，所以A为左子树的根节点，即A为root的leftchild；同理root的rightchild为G。

  第四步：我们可以根据上面的步骤找到B的左子树和右子树，以及C的左子树和右子树，然后分别求出左右子树的根节点。以此类推，只要求出根节点及其leftchild和rightchild，剩下的过程都是递归的，最后我们就可以还原整个二叉树。

           E
      A        G
       C      F
      B D

把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。
森林中含有数的个数，就是二叉树右孩子的数目+1，这里为2

编辑于 2015-02-04 15:59:25 回复(2)
菜小豆头像 菜小豆
简单来说就是根节点开始算起，右支上的所有右节点的个数
发表于 2015-09-04 19:13:31 回复(0)
觉醒之力头像 觉醒之力

树的结构是：

如何将树转换为森林

发表于 2017-03-12 15:32:40 回复(2)
Athrun丶头像 Athrun丶
所以是2个  一个是EACBD   一个GF  
只看主根上右支的所有右节点的个数
发表于 2018-07-19 14:06:23 回复(0)
爱如少年L头像 爱如少年L
后序序列最后一个元素即原二叉树的根，即本题中的E，在根据中序序列可以确定根E两边的序列，再以此类推，推出原二叉树
树转二叉树，看是否有右分支。
发表于 2018-06-15 18:18:34 回复(0)
木易口肃头像 木易口肃
    森林转化成二叉树：把所有根节点当做兄弟，保证任意一个节点的左指针域指向第一个孩子，右指针域指向它的下一个兄弟。
    针对二叉树对应的树林包括多少棵树：只需看根节点的右子树有几个节点。本题为2。
发表于 2018-05-23 21:57:01 回复(0)
kainever头像 kainever
树 转换成二叉树 就是通过孩子兄弟表示法:

二叉树转换成树 == > http://img.blog.csdn.net/20130916192205156

而二叉树转换成森林的意思：这棵二叉树可以转换成多少棵树
将二叉树根结点与其右孩子之间的连线，以及沿着此右孩子的右链连续不继搜索到的右孩子间的连线抹掉。这样就得到了若干棵根结点没有右子树的二叉树。比如这道题目的根节点右子树的GF 如果G的右子树不为空，那么又可以进行拆分

发表于 2015-08-02 16:52:14 回复(0)
HHhhh9头像 HHhhh9
B
森林转换为树，首先将有右孩子的结点与右孩子相连，如果结点的右孩子也有右孩子，继续将结点与右孩子的右孩子相连，以此类推。最后删除所有结点与其右孩子之间的连线，所得树为最终结果。
发表于 2018-08-07 14:51:52 回复(0)
相信自己！头像 相信自己！
树转换成二叉树，结点的两个链域分别指向该节点的第一个孩子结点和下一个兄弟节点，根据定义可知，任何一棵和数对应的二叉树，其右子树必为空！
森林转换成二叉树，第二树的根作为上一棵树根的右孩子。

所以根据右子树上有孩子的个数可判断森林中树的个数

发表于 2016-08-30 09:40:19 回复(0)
7秒記憶_47692头像 7秒記憶_47692
考察二叉树与森林的转换，考察孩子兄弟表示法
发表于 2015-08-25 11:20:42 回复(0)
提交观点

问题信息

树 迅雷
上传者：A-Winter
难度：
10条回答 8017浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号