二叉樹的周遊

二叉樹的周遊：對樹中所有節點的資訊通路，即依次對樹中每個節點通路，對所有的節點的通路稱為周遊。二叉樹的兩種周遊方式深度優先和廣度優先，深度優先一般使用遞歸，廣度優先一般使用隊列，一般情況下能用遞歸實作的算法都能用堆棧來實作（其實遞歸也是堆棧，函數調用函數—>函數調用棧）

（1）廣度優先周遊—也叫層序周遊，使用隊列來操作

def layer_travel(self, root):
        """利用隊列實作樹的層次周遊"""
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print node.elem,
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)           

（2）深度優先周遊

對于一顆二叉樹，深度優先搜尋是沿着樹的深度周遊樹的節點，盡可能深的搜尋樹的分支，深度周遊有重要的三種方式：先序周遊、中序周遊、和後序周遊。

—先序周遊 在先序周遊中，我們先通路根節點，然後遞歸使用先序周遊通路左子樹，再遞歸使用先序周遊通路右子樹

根節點->左子樹->右子樹

def preorder(self, root):
      """遞歸實作先序周遊"""
      if root == None:
          return
      print root.elem
      self.preorder(root.lchild)
      self.preorder(root.rchild)           

–中序周遊 在中序周遊中，我們遞歸使用中序周遊通路左子樹，然後通路根節點，最後再遞歸使用中序周遊通路右子樹

左子樹->根節點->右子樹

def inorder(self, root):
      """遞歸實作中序周遊"""
      if root == None:
          return
      self.inorder(root.lchild)
      print root.elem
      self.inorder(root.rchild)           

def postorder(self, root):
      """遞歸實作後續周遊"""
      if root == None:
          return
      self.postorder(root.lchild)
      self.postorder(root.rchild)
      print root.elem