遍历方案
　从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
　1).访问结点本身(N)
　2).遍历该结点的左子树(L)
　3).遍历该结点的右子树(R)

有次序：
　NLR、LNR、LRN

遍历的命名

　根据访问结点操作发生位置命名：
NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ――访问结点的操作发生在遍历其左右子树之前。
LNR：中序遍历(InorderTraversal) ――访问结点的操作发生在遍历其左右子树之中(间)。
LRN：后序遍历(PostorderTraversal) ――访问结点的操作发生在遍历其左右子树之后。

注：由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

遍历算法

1)．先序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
a.访问根结点
b.遍历左子树
c.遍历右子树

2)．中序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
a.遍历左子树
b.访问根结点
c.遍历右子树

3)．后序遍历得递归算法定义：
若二叉树非空，则依次执行如下操作：
a.遍历左子树
b.遍历右子树
c.访问根结点

一、二叉树的递归遍历：

复制代码 代码如下:

-- coding: utf - 8 - -

class TreeNode(object):

def __init__(self, left=0, right=0, data=0):  
    self.left = left  
    self.right = right  
    self.data = data  

class BTree(object):

def __init__(self, root=0):  
    self.root = root  

def is_empty(self):  
    if self.root is 0:  
        return True  
    else:  
        return False  

def preorder(self, treenode):  
    '前序（pre-order，NLR）遍历'  
    if treenode is 0:  
        return  
    print treenode.data  
    self.preorder(treenode.left)  
    self.preorder(treenode.right)  

def inorder(self, treenode):  
    '中序（in-order，LNR'  
    if treenode is 0:  
        return  
    self.inorder(treenode.left)  
    print treenode.data  
    self.inorder(treenode.right)  

def postorder(self, treenode):  
    '后序（post-order，LRN）遍历'  
    if treenode is 0:  
        return  
    self.postorder(treenode.left)  
    self.postorder(treenode.right)  
    print treenode.data  

node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 'root')

bt = BTree(root)

print u'''

生成的二叉树

------------------------

root

7 8

6

2 5

1 3 4

-------------------------

'''
print '前序（pre-order，NLR）遍历 ：\n'
bt.preorder(bt.root)

print '中序（in-order，LNR) 遍历 ：\n'
bt.inorder(bt.root)

print '后序（post-order，LRN）遍历 ：\n'
bt.postorder(bt.root)