二叉树的恢复和遍历

二叉树的遍历

先序遍历（前序遍历） 遍历顺序 根节点——先序遍历左子树——先序遍历右子树

中序遍历 遍历顺序 中序遍历左子树——根节点——中序遍历右子树

后序遍历 遍历顺序 后序遍历左子树——后序遍历右子数——根节点

在做二叉树的恢复时，一定要清楚的掌握二叉树的遍历的概念。任何复杂的二叉树都是有基本的二叉树构成。只要明白了二叉树三种遍历的基本概念，就可以快速并准确的写出先序，中序，后序遍历。

二叉树的恢复

根据一道期末考试的题目来分析一下二叉树的恢复 已知一课二叉树的先序序列为KEFJIHGDCAB，中序序列为JFHIGEDKABC，请画出这课二叉树，写出它的后序序列。 解析： 根据先序遍历的基本概念，由先序序列可以知道该二叉树的根节点为K. 该题目左子树含有JFHIGED,右子树含有ABC 将左子树看成一个新题目就是：先序序列是EFJIHGD，中序序列为JFHIGED。 则该二叉树的根节点为E，左子树含有JFHIG，右子树含有D 将此时的左子树又看成一道新题目：先序序列是FJIHG，中序序列是JFHIG。 此二叉树根节点为F，左子树含有J，右子树含有HIG。 将此时的右子树看成一道新题目：先序序列是IHG，中序序列是HIG。 则该二叉树的根节点为I，左子树含有H，右子树含有G。 如图所示： 将右子树看成一个新题目就是：先序序列为CAB，中序序列为ABC。 则根节点为C，左子树中含有AB。 则根节点为A，没有左子树，右子树为B。 如图所示：

将左右子树合起来就是完整的二叉树。如图：