引入
前面讲到了二叉搜索树以及它的一些基本操作（插入，搜索，删除），可是我们要怎么知道这些操作已经被执行了呢？换句话说，怎样来描述二叉树的结构。这里我们又用到了遍历。
和图的遍历一样，我们也需要逐个访问每一个节点，但跟图不同的是，二叉树的遍历是从根节点开始的，而非任意节点。根据二叉树的结构我们知道，每棵二叉树都是由三部分组成的：根节点，左子树和右子树。而根节点的左右子树也是由这三部分组成，所以二叉树的遍历问题也是可以用分治来解决的，即遍历一颗二叉树 = 访问根节点 + 遍历根节点的左子树 + 遍历根节点的右子树。
进而我们写出下面的递归关系式：
其中 n(T) 代表的是二叉树 T 的节点个数。因为当 T 为空树时，我们不执行任何操作，所以这里的 S(0) = 0，即递归的出口。
三种遍历法
根据左子树、右子树和根节点的遍历顺序，我们可以把遍历方式分为前序、中序和后序遍历。
前序遍历
前序遍历是先访问根节点，然后遍历左子树，最后遍历右子树。下面这张动图展示了前序遍历的整个过程。
代码实现：
def pre_order(T):
print(T.value, end=' ')
if T.left:
pre_order(T.left)
if T.right:
pre_order(T.right)
中序遍历
中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。下面这张动图展示了中序遍历的整个过程。
代码实现：
def in_order(T):
if T.left:
in_order(T.left)
print(T.value, end=' ')
if T.right:
in_order(T.right)
后序遍历
后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。下面这张动图展示了后序遍历的整个过程。
代码实现：
def post_order(T):
if T.left:
post_order(T.left)
if T.right:
post_order(T.right)
print(T.value, end=' ')
因为遍历需要访问的节点数总是为 n，所以无论是哪种遍历方式，其复杂度都为 Θ(n)。
→ 本节全部代码 ←
