设某二叉树的前序遍历序列为:ABCDEFGHI,中序遍历序列为:BCAEDGHFI,则二叉树的后序序列为
时间: 2023-06-27 18:07:08 浏览: 162
根据二叉树遍历的性质,可以得到以下信息:
- 前序遍历的第一个节点为根节点,即A为根节点。
- 中序遍历中,A将树分成了左右两个子树,左子树为BCAE,右子树为GHFI。
- 同样地,前序遍历中,A之后的三个节点BCD为左子树的前序遍历序列,EFGHI为右子树的前序遍历序列。
根据这些信息,可以递归地构建二叉树并求出后序遍历序列:
1. 对于左子树,前序遍历序列为BCD,中序遍历序列为BCAE,递归构建左子树并求出后序遍历序列CDABE。
2. 对于右子树,前序遍历序列为EFGHI,中序遍历序列为GHFI,递归构建右子树并求出后序遍历序列GIFHE。
3. 将左右子树的后序遍历序列拼接到根节点后面,得到后序遍历序列CDABEGIFHEA。
因此,该二叉树的后序遍历序列为CDABEGIFHEA。
相关问题
设某二叉树的前序遍历序列为:ABCDEFGHI,中序遍历序列为:BCAEDGHFI,则该二叉树的后序序列为 填空 1 (直接输入大写字母,不需要空格隔开)
根据前序遍历序列的定义,该二叉树的根节点为A。因此,A在后序遍历序列的最后一个位置。
根据中序遍历序列的定义,左子树的节点都在根节点的左边,右子树的节点都在根节点的右边。因此,B、C、A、E、D在前序遍历序列中的位置与中序遍历序列中的位置相同,而G、H、F在前序遍历序列中的位置分别是DEFGHI,与中序遍历序列中的位置IHGFED相反。
根据二叉树后序遍历的定义,先输出左子树的节点,再输出右子树的节点,最后输出根节点。因此,该二叉树的后序遍历序列为:填空1为:BCAEHGFDI。
已知二叉树的前序遍历序列为ABDCEFG,中序遍历序列是DBCAFEG,则其后序遍历序列为
根据二叉树遍历的性质,先求出二叉树的左右子树分布情况:
前序遍历:A B D C E F G
中序遍历:D B C A F E G
可以看出,根节点为A,因此左子树的前序遍历为B D,中序遍历为D B,右子树的前序遍历为C E F G,中序遍历为F E G。
将左右子树分别递归求解,直到子树为空,此时对应的后序遍历序列即为:
左子树的后序遍历序列:D B
右子树的后序遍历序列:F E G C
根节点的后序遍历序列:A
因此,整个二叉树的后序遍历序列为:DBFEGCA。