二叉树的遍历

二叉树是由3个基本单元组成：根节点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。假如以L、D、R分别表示遍历左子树、访问根节点和遍历右子树，则可以有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。若限定先左后右，则只有前3种情况，分别称之为先（根）序遍历、中（根）序遍历和后（根）序遍历。
下面通过一个例子来讲解，现有一个表达式：a + b * (c - d) - e / f，则该表达式可表示为如下二叉树：

则对其进行遍历

• 先序遍历结果为：-+a*b-cd/ef。
• 中序遍历结果为：a+b*c-d-e/f。
• 后序遍历结果为：abcd-*+ef/-。

从表达式来看，以上三个序列恰好为表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。