二叉树前中后序遍历

算法
  • 二叉树的前中后序是相对于根节点来说的
  • 前根序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。

    ABDHECFG

  • 中根序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。

    HDBEAFCG

  • 后根序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点。

    HDEBFGCA

  • 已知一棵二叉树的前根序序列和中根序序列，构造该二叉树的过程如下：

    • 根据前根序序列的第一个元素建立根结点；
    • 在中根序序列中找到该元素，确定根结点的左右子树的中根序序列；
    • 在前根序序列中确定左右子树的前根序序列；
    • 由左子树的前根序序列和中根序序列建立左子树；
    • 由右子树的前根序序列和中根序序列建立右子树。

  • 已知一棵二叉树的后根序序列和中根序序列，构造该二叉树的过程如下：

    • 根据后根序序列的最后一个元素建立根结点；
    • 在中根序序列中找到该元素，确定根结点的左右子树的中根序序列；
    • 在后根序序列中确定左右子树的后根序序列；
    • 由左子树的后根序序列和中根序序列建立左子树；
    • 由右子树的后根序序列和中根序序列建立右子树。