一个二叉树的先序序列是ABDGCEFH,中序序列是DGBAECHF,那么他的后序序列是什么(请给出图示证明)
时间: 2024-05-19 12:15:23 浏览: 63
给定二叉树前序和中序求后序
该二叉树的后序序列为:DGEBHFCA。
证明如下图所示:
首先,从先序序列中得知根节点为A,然后在中序序列中找到根节点A的位置,将中序序列分为左子树和右子树,左子树的中序序列为DGB,右子树的中序序列为ECHF。
根据左右子树的大小,可以将先序序列分成两部分,分别为左子树的先序序列ABDGC和右子树的先序序列FEH。
对于左子树,根据同样的方法,可以得到左子树的根节点为B,左子树的中序序列为DG,左子树的先序序列为BDG,进而得到左子树的后序序列为DGB。
对于右子树,同样也可以得到右子树的根节点为F,右子树中序序列为EH,右子树的先序序列为FEH,进而得到右子树的后序序列为EHF。
综合左右子树的后序序列,可以得到整棵树的后序序列为DGEBHFCA。
阅读全文