二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)丑念，很多其它數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹的基礎(chǔ)演變而來的。對于二叉樹浪规，有深度遍歷和廣度遍歷或听，深度遍歷有前序、中序以及后序三種遍歷方法笋婿，廣度遍歷即我們平常所說的層次遍歷誉裆。因為樹的定義本身就是遞歸定義，因此采用遞歸的方法去實現(xiàn)樹的三種遍歷不僅容易理解而且代碼很簡潔缸濒，而對于廣度遍歷來說足丢，需要其他數(shù)據(jù)結(jié)構(gòu)的支撐，比如堆了庇配。所以斩跌，對于一段代碼來說，可讀性有時候要比代碼本身的效率要重要的多捞慌。

1.png

四種主要的遍歷思想為：
1耀鸦、深度優(yōu)先遍歷
前序遍歷：根結(jié)點 ---> 左子樹 ---> 右子樹 （中，左啸澡，右的遍歷順序）
中序遍歷：左子樹 ---> 根結(jié)點 ---> 右子樹 （左揭糕、中萝快、右的遍歷順序）
后序遍歷：左子樹 ---> 右子樹 ---> 根結(jié)點 （左、右著角、中的遍歷順序）
2揪漩、廣度優(yōu)先遍歷
層次遍歷：只需按層次遍歷即可
例如，求下面二叉樹的各種遍歷
遍歷的結(jié)果 ：
前序遍歷：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 的代碼實現(xiàn)：

class TreeNode(object):
    #data:節(jié)點值
    #left:左子節(jié)點(默認為None)
    #right：右子節(jié)點(默認為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):
    #添加葉節(jié)點
        treenode = TreeNode(element)
        if self.root.element == None:
            #如果樹是空的就給書添加根節(jié)點
            self.root = treenode
            self.myQueue.append(self.root)
        else:
            #將子節(jié)點添加到列表的首位
            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):
        '''利用隊列實現(xiàn)樹的層次遍歷'''
        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__':
  """主函數(shù)"""
  elems = range(10)      #生成十個數(shù)據(jù)作為樹節(jié)點
  tree = Tree()     #新建一個樹對象
  for elem in elems:
    tree.add_Treenode(elem)      #逐個添加樹的節(jié)點
  print '隊列實現(xiàn)層次遍歷:'
  tree.level_queue(tree.root)
  print '\n\n遞歸實現(xiàn)先序遍歷:'
  tree.front_digui(tree.root)
  print '\n遞歸實現(xiàn)中序遍歷:'
  tree.middle_digui(tree.root)
  print '\n遞歸實現(xiàn)后序遍歷:'
  tree.later_digui(tree.root)