已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为A．GEDHFBCA B．DGEBHFCA C．ABCDEFGH D．ACBFEDHG
- AGEDHFBCA
- BDGEBHFCA
- CABCDEFGH
- DACBFEDHG
问题
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则
参考解析：
遍历是按照一定规则对树中全部结点逐一访问的方法。二叉树可由根结点、左子树和右子树三个部分组成。根据对根结点访问的先后顺序，可将遍历方法分为先序遍历、中序遍历和后序遍历三种。先序遍历首先访问根结点，再先序遍历左子树，最后先序遍历右子树，可见遍历是一个递归的过程。求树的遍历这种问题的关键在于认清每棵子树的根结点的访问顺序。题目给出了一棵树的先序遍历和中序遍历的结点顺序，先序遍历的第一个结点为整棵树的根结点，即根结点为A，而在中序遍历的顺序中，结点A的前面还有DBGE四个结点，表示这四个结点构成以A为结点的二叉树的左子树，同理，中序遍历中A结点后面的CHF三个结点构成以A为结点的二叉树的右子树。于是原来的对一棵二叉树的分析变为对该二叉树的左右子树的分析。以左子树为例，左子树结点的先序遍历为BDEG，中序遍历为DBGE，该子树的根结点为B，B结点的左子树为一个结点D，右子树为以E为根结点，结点G是E的左孩子。同理，可对CHF三个结点进行分析。最后得到整棵树的结构后，按照后序遍历写出所有结点的顺序：DGEBHFCA。
分类：其他
相关推荐
-
1、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二
设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。ABADCBBCDACCDABDCBDA
-
2、已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为（）AGEDHFBCABDGEBHFCACABCDEFGHDACBFEDHG
-
3、对一棵二叉树的先序遍历、后序遍历和中序遍历所产生的序列中，所有叶结点的先后顺
对一棵二叉树的先序遍历、后序遍历和中序遍历所产生的序列中，所有叶结点的先后顺序是 ( ) 。A各不相同B先序遍历与后序遍历相同C完全相同D后序遍历与中序遍历相同
-
4、已知一棵二叉树前序遍历和中序遍历分别为ABDEFGCHI和DBFEGACIH
已知一棵二叉树前序遍历和中序遍历分别为ABDEFGCHI和DBFEGACIH，则该二叉树的后序遍历为A．DFGEBHICA B．DGEBHFCAI C．DFGEBIHCA D．DGEBFIHCAADFGEBHICA BDGEBHFCAI CDFGEBIHCA DDGEBFIHCA
-
5、已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH~DBGEACI-IF
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH~DBGEACI-IF，则该二叉树的后序遍历为______。AGEDHFBCABDGEBHFCACABCDEFGHDACBFEDHG
-
6、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中
在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结果。A正确B错误