已知一棵二叉树的中序遍历是DEBACle,后序遍历是DABEC,求前序遍历

用户头像
来自沈阳师范大学-姜莉薇发布于:2024-11-20 00:13:27
1. 首先明确后序遍历的顺序是“左子树 - 右子树 - 根节点”,所以后序遍历序列“DABEC”中最后一个字符“C”就是这棵二叉树的根节点。 2. 然后根据中序遍历的顺序“左子树 - 根节点 - 右子树”,在中序遍历序列“DEBAC”中,根节点“C”左边的“DEBA”就是根节点“C”的左子树部分,右边没有字符说明右子树为空。 3. 接着看左子树部分,后序遍历中左子树部分是“DABE”,所以“E”是左子树的根节点。再看中序遍历的左子树“DEBA”,“E”左边的“D”是其左子树,右边的“BA”是其右子树。 4. 对于“E”的右子树“BA”,后序遍历是“AB”,所以“B”是右子树的根节点,中序遍历中“B”左边的“A”就是“B”的左子树。 综上,这棵二叉树的前序遍历顺序是“CEDBA”。
点赞 (0) 回复
发布回复
点击图片