Question

若某二叉树的先序遍历dabec和中序遍历debac请画出该树并写出它的后序遍历?

Answer 1

问：若某二叉树的先序遍历dabec和中序遍历debac请画出该树并写出它的后序遍历?

答：该二叉树的后序遍历为：edcbaf。具体推导过程如下：1. 先序遍历的第一个字符是根节点，即 d；2. 在中序遍历中找到根节点 d 的位置，在其左边的是其左子树的中序遍历 deba，右边是其右子树的中序遍历 c；3. 根据左子树的中序遍历 deba 和先序遍历 dabec，可以得到左子树的先序遍历 dae 和中序遍历 deba；4. 对左子树递归执行步骤 2 和步骤 3，得到左子树的结构和后序遍历 edcb；5. 对右子树递归执行步骤 2 和步骤 3，得到右子树的结构和后序遍历 f；6. 将根节点 d 放在最后面，得到二叉树的后序遍历 edcbaf。