早教吧作业答案频道 -->数学-->
一颗二叉树节点的前序序列是ABDEGCFHI,中序序列为DBGEACHFI,则该二叉树节点的后序序列是什么?有图会理解的更好,
题目详情
一颗二叉树节点的前序序列是ABDEGCFHI,中序序列为DBGEACHFI,则该二叉树节点的后序序列是什么?
有图会理解的更好,
有图会理解的更好,
▼优质解答
答案和解析
根据相关概念,前序遍历的第一个结点一定是根结点(类似问题如果给出的是后序则最后一个一定是根结点).于是可以据此将中序序列由根划分出左右子树来.如是递归下去,最后总能构造出完整的树来,并写出所求的后序序列.
以你给的问题为例:整棵树的根结点为前序的第一个点即A,于是根据中序可知左子树含结点DBGE、右子树含结点CHFI.分别递归分析左子树和右子树:左子树的根为前序中“BDEG”段内的第一个结点即B,右子树根为C…………类似一直进行到最小情况为止,树就可以构造出来了.
建议做完问题后可以在计算机上写个递归程序(以前序 中序为输入,后序为输出)加深一下对这种问题的理解.
以你给的问题为例:整棵树的根结点为前序的第一个点即A,于是根据中序可知左子树含结点DBGE、右子树含结点CHFI.分别递归分析左子树和右子树:左子树的根为前序中“BDEG”段内的第一个结点即B,右子树根为C…………类似一直进行到最小情况为止,树就可以构造出来了.
建议做完问题后可以在计算机上写个递归程序(以前序 中序为输入,后序为输出)加深一下对这种问题的理解.
看了 一颗二叉树节点的前序序列是A...的网友还看了以下:
设森林F对应的二叉树为B,它有m个节点,B的根为p,p的右子树上的节点个数为 n,森林F中第一棵树的 2020-05-23 …
设森林9中有3棵树,其第一、第二和第三棵树的节点个数分别是n1、n2和n3,则与森林F对应的二叉树根 2020-05-23 …
设森林F中有三棵树,第一、第二和第三棵树的节点个数分别为M1、M2和M3。与森林F对应的二叉树根节点 2020-05-23 …
设森林F中有三棵树T1、T2、T3,节点个数分别为m1、m2、m3。与森林F对应的二叉树根结点的右子 2020-05-24 …
设森林F对应的二叉树为B,它有m个节点,B的根为P,P的右子树上的节点个数为n,森林F中第一棵树的节 2020-05-24 …
设森林F中有3棵树,其第一、第二和第三棵树的节点个数分别是n1、n2和n3,则与森林F对应的二叉树根 2020-05-24 …
某大型行业网络,其一级网大区中心节点下属5个二级节点,每个二级节点到大区中心的数据业务流量为2Mbp 2020-05-31 …
设f(t)=lim(x趋近于无穷)(t^2+t)(1+1/x)^-2tx,则f'(t)=第二题设f 2020-06-04 …
作文小学四年级下册一种树第一小写树的名称第二小节树的作用第三小节树的特点要求字数在250~400超过 2020-11-24 …
设F是一个森林,B是由F按自然对应关系转换而得到的二叉树,F中有n个非终端节点,则B中的右子树为空的 2021-01-02 …