设某二叉树的前序遍历序列为:ABCDEFGHI,中序遍历序列为:BCAEDGHFI,则该二叉树的后序序列为 填空 1 (直接输入大写字母,不需要空格隔开)
时间: 2023-12-06 11:41:50 浏览: 91
二叉树 根据前序中序求后序遍历
根据前序遍历序列的定义,该二叉树的根节点为A。因此,A在后序遍历序列的最后一个位置。
根据中序遍历序列的定义,左子树的节点都在根节点的左边,右子树的节点都在根节点的右边。因此,B、C、A、E、D在前序遍历序列中的位置与中序遍历序列中的位置相同,而G、H、F在前序遍历序列中的位置分别是DEFGHI,与中序遍历序列中的位置IHGFED相反。
根据二叉树后序遍历的定义,先输出左子树的节点,再输出右子树的节点,最后输出根节点。因此,该二叉树的后序遍历序列为:填空1为:BCAEHGFDI。
阅读全文