二叉树：前(先)序、中序、后序遍历

遍历二叉树：L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则先(根)序遍历二叉树的顺序是DLR，中(根)序遍历二叉树的顺序是LDR，后(根)序遍历二叉树的顺序是LRD。还有按层遍历二叉树。这些方法的时间复杂度都是O(n)，n为结点个数。
如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的前序，T中结点的后序就是T2中结点的中序。任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序不发改变。设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是n在m的左方。前序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树；中序序列和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树；前序序列和后序序列相同的二叉树为空树或仅有一个结点的二叉树。
假设我们有一个包含值的value和指向两个子结点的left和right的树结点结构。我们可以写出这样的过程：

visit(node)
    print node.value
    if node.left  != null then visit(node.left)
    if node.right!= null then visit(node.right)

这样会用前序打印出树中的值。在前序，每个结点在访问它的子结点之前访问。类似地，如果打印语句在最后，每个结点在访问他的子节点之后访问，树中的值会用后序来打印。在这两种情况中，左子树中的值比右子树中得值先打印。

visit(node)
    if node.left  != null then visit(node.left)
    print node.value
    if node.right!= null then visit(node.right)

最后，上面的中序遍历，每个结点在访问左子树和右子树之间访问。这在遍历 二叉搜索树时很常用，因为它能用递增的顺序来遍历所有的值。
为什么呢？如果/n/是二叉搜索树的结点，那么/n/的左子树的所有结点的值都比n的值要小，而且/n/的右子树的所有节点的值都比n的值要大。因此，如果我们顺序遍历左子树，然后访问/n/，然后顺序遍历右子树。我们就已经循序访问了整个树。
后序遍历伪代码如下：

visit(node)
    if node.left  != null then visit(node.left)
    if node.right!= null then visit(node.right)
    print node.value