python实现二叉树的遍历

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们平常所说的层次遍历。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁，而对于广度遍历来说，需要其他数据结构的支撑，比如堆了。所以，对于一段代码来说，可读性有时候要比代码本身的效率要重要的多。

四种主要的遍历思想为：
1、深度优先遍历
前序遍历：根结点 ---> 左子树 ---> 右子树 （中，左，右的遍历顺序）
中序遍历：左子树 ---> 根结点 ---> 右子树 （左、中、右的遍历顺序）
后序遍历：左子树 ---> 右子树 ---> 根结点 （左、右、中的遍历顺序）
2、广度优先遍历
层次遍历：只需按层次遍历即可
例如，求下面二叉树的各种遍历
遍历的结果 ：
前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
层次遍历：1 2 3 4 5 6 7 8

python 的代码实现：

class TreeNode(object):
    #data:节点值
    #left:左子节点(默认为None)
    #right：右子节点(默认为None)
    def __init__(self,element=None,left=None,right=None):
        self.element=element
        self.left=left
        self.right=right
    def __str__(self):
        return str(self.element)
class Tree(object):
    #定义树的类
    def __init__(self):
        self.root = TreeNode()
        self.myQueue = []
    def add_Treenode(self,element):
    #添加叶节点
        treenode = TreeNode(element)
        if self.root.element == None:
            #如果树是空的就给书添加根节点
            self.root = treenode
            self.myQueue.append(self.root)
        else:
            #将子节点添加到列表的首位
            childNode = self.myQueue[0]
            if childNode.left == None:
                childNode.left = treenode
                self.myQueue.append(childNode.left)
            else:
                childNode.right = treenode
                self.myQueue.append(childNode.right)
                self.myQueue.pop(0)

    def front_digui(self,root):#前序遍历
        if root == None:
            return
        print(root.element)
        self.front_digui(root.left)
        self.front_digui(root.right)

    def middle_digui(self,root):#中序遍历
        if root == None:
            return
        self.middle_digui(root.left)
        print(root.element)
        self.middle_digui(root.right)

    def later_digui(self,root):#后序遍历
        if root == None:
            return
        self.later_digui(root.left)
        self.later_digui(root.right)
        print root.element

    def level_queue(self, root):
        '''利用队列实现树的层次遍历'''
        if root == None:
            return
        myQueue = []
        node = root
        myQueue.append(node)
        while myQueue:
            node = myQueue.pop(0)
            print node.element,
            if node.left != None:
                myQueue.append(node.left)
            if node.right != None:
                myQueue.append(node.right)

if __name__ == '__main__':
  """主函数"""
  elems = range(10)      #生成十个数据作为树节点
  tree = Tree()     #新建一个树对象
  for elem in elems:
    tree.add_Treenode(elem)      #逐个添加树的节点
  print '队列实现层次遍历:'
  tree.level_queue(tree.root)
  print '\n\n递归实现先序遍历:'
  tree.front_digui(tree.root)
  print '\n递归实现中序遍历:'
  tree.middle_digui(tree.root)
  print '\n递归实现后序遍历:'
  tree.later_digui(tree.root)