前言
作为一种经典的非线形数据结构，树的应用十分广泛。其中二叉树是一种非常典型的树结构，即每个节点最多只有左右两个分支。在这篇文章中，我会总结一下关于二叉树结构的一个重要问题:遍历。和线形结构不同，二叉树的遍历存在多种方式，最主要的3种就是前序，中序以及后序遍历。当然还有其他方式比如层次遍历等。OK，我们进入正题。
假设我们现在有这样一棵简单的二叉树。
让我们用python代码快速实现一下这棵树。
#!/usr/bin/env python
#define the class of node
class Binary_Tree_Node():
def __init__(self,data):
self.data=data
self.lchild=None #left side node
self.rchild=None #right side node
#generate node
a=Binary_Tree_Node("A")
b=Binary_Tree_Node("B")
c=Binary_Tree_Node("C")
d=Binary_Tree_Node("D")
e=Binary_Tree_Node("E")
f=Binary_Tree_Node("F")
g=Binary_Tree_Node("G")
#link them
e.lchild=a
e.rchild=g
a.rchild=c
c.lchild=b
c.rchild=d
g.rchild=f前序遍历
前序遍历的逻辑是从根节点出发(root),先递归地遍历左子树，然后再递归地遍历右子树。
以上面这棵树作为例子，第一步从E出发，接下来进入左子树，到根节点A，再去看A的左子树，发现没有，再进入右子树，到根节点C，然后左子树，到节点B，发现已经没有继续的节点。就进入右子树，到节点D，同样发现没有继续的节点。到此整棵左子树遍历结束。
然后进入最初根节点E的右子树，同样先去找左子树，发现为空。然后进入右子树，根节点G，继续寻找左子树，发现为空。然后进入右子树，根节点F。没有后续节点。结束。
整个遍历顺序就是E->A->C->B->D->G->F。
用代码来实现一下，本质就是使用递归。
#the same script with above code block
def prima_order(root):
if root:
print(root.data,end="->") #root
prima_order(root.lchild) #recursion of left child tree
prima_order(root.rchild) #recursion of right child tree
return 'end'
if __name__=='__main__':
print(prima_order(e))
中序遍历
中序遍历的逻辑是先递归遍历左子树，再到中间的根节点，最后是右子树。也就是将根节点放在中间的位置。
同样还是以上面这棵树为例。先进入左子树,即以A为根节点的左子树。仔细观察后发现以A为根节点的树并没有左子树，因此直接到A这个根节点，再进入其右子树（以C为根节点）。发现其有左子树B, 没有后续，再进入根节点C，再进入右子树，只有一个节点D。到此最初根节点E下的左子树已经遍历完成。
然后就自然是E节点自己。
然后进入右子树。发现以G为根节点的树同样没有左子树，那么直接到G自己，再到右子树，发现只有一个F，遍历完后结束。
所以最终的遍历结果为A->B->C->D->E->G->F
以下是代码
def mid_order(root):
if root:
mid_order(root.lchild)
print(root.data,end='->')
mid_order(root.rchild)
return 'end'后序遍历
根据前面两种遍历方式的逻辑以及对应的名字，其实我们已经很容易猜到后序遍历的遍历逻辑了。
即先遍历左子树，再遍历右子树，最后访问自己。
还是以上面的树作为例子。首先进入以A为根节点的左子树，发现没有左子树，那就进入右子树（以C为根节点），同样先去左子树B，再去右子树D，最后回到根C，再到上一级的根节点A。到这里整棵树的左子树遍历完毕。然后进入整棵树的右子树（以G为根节点)。先去左子树，发现为空，然后到右子树F，最后回到根节点G，到此右子树叶完成遍历，最后到根节点E。结束
最终的遍历结果为B->D->C->A->F->G->E
以下是代码，本质就是调换一下递归的顺序罢了。
def back_order(root):
if root:
back_order(root.lchild)
back_order(root.rchild)
print(root.data,end='->')
return 'end'上面介绍了三种最基本的遍历方式，最后放一道基础的笔试题来帮助大家的理解。
Q:假设我们已知一棵二叉树的后序遍历结果为B->F->E->G->C->D->A,中序遍历结果为B->A->D->E->F->C->G?。请问这棵二叉树的前序遍历结果为什么？
A:A->B->D->C->E->F->G