二叉树的遍历

所谓的遍历是指按一定的规律和次序访问树中的各个节点，而且每个节点仅被访问一次。遍历一般按照从左到右的顺序，共有 4 种遍历方法：前序遍历、中序遍历、后序遍历、层次遍历。

前序遍历

先序遍历：先访问根节点，再访问左子树，最后访问右子树。

根节点 --> 左子树 --> 右子树

中序遍历

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

左子树 --> 根节点 --> 右子树

后序遍历

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

左子树 --> 右子树 --> 根子树

层次遍历

层次遍历：每一层从左到右访问每一个节点。

例如：求下列二叉树的各种遍历

先序遍历结果：A B D F E C G H I

中序遍历结果：D B E F A G H C I

后序遍历结果：D E F B H G I C A

层次遍历结果：A B C D F G I E H

例如：已知节点的前序序列为ABCDEFG，中序序列为CBEDAFG。构造出二叉树。过程见下图：

前后序找根，中序分左右。