若某二叉树的先序遍历序列和中序遍历序列分别为PBECD、BEPCD,则该二叉树的后序遍历序列为多少

托钵僧 · 2018-4-30 02:08:18

EBDCP

agui913011203 · 2018-4-30 02:08:17

EBDCP聽，树型是这样的

ctqcbd · 2018-4-30 02:08:16

前后，后续是前后中。
如果两个子树都有孩子的话，那么按照上面的规定，就肯定不可能成立的，所以是特殊情况，只有一个孩子。

酋长的爷爷 · 2018-4-30 02:08:15

介绍一下这类问题的求解方法：
前序的第一个结点一定是根结点（如果给了后序则最后一个结点一定是根结点），由此在中序序列可划分出“（左子树）根（右子树）”结构。再对左、右子树同理递归考虑。
你的问题给了前序PBECD和中序BEPCD，于是根结点一定是P，中序可视为(BE)P(CD)；
左子树在前序中顺序为BE，于是左子树根为B，于是左子树中序可视为B(E)；
同理右子树中序可视为C(D)。于是可以构造出二叉树(B(E))P(C(D))，对其后序遍历即可。

若某二叉树的先序遍历序列和中序遍历序列分别为PBECD、BEPCD,则该二叉树的后序遍历序列为多少

4 个回复