## 二叉樹的遍歷 樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結點的信息的訪問，即依次對樹中每個結點訪問一次且僅訪問一次，我們把這種對所有節點的訪問稱為遍歷（traversal）。那么樹的兩種重要的遍歷模式是深度優先遍歷和廣度優先遍歷,**深度優先一般用遞歸，廣度優先一般用隊列。一般情況下能用遞歸實現的算法大部分也能用堆棧來實現。** ## 深度優先遍歷 對于一顆二叉樹，深度優先搜索(Depth First Search)是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。 那么深度遍歷有重要的三種方法。這三種方式常被用于訪問樹的節點，它們之間的不同在于訪問每個節點的次序不同。這三種遍歷分別叫做先序遍歷（preorder），中序遍歷（inorder）和后序遍歷（postorder）。我們來給出它們的詳細定義，然后舉例看看它們的應用。 1.先序遍歷 在先序遍歷中，我們先訪問根節點，然后遞歸使用先序遍歷訪問左子樹，再遞歸使用先序遍歷訪問右子樹 根節點->左子樹->右子樹 ~~~ def preorder(self, root): """遞歸實現先序遍歷""" if root == None: return print root.elem self.preorder(root.lchild) self.preorder(root.rchild) ~~~ 2.中序遍歷 在中序遍歷中，我們遞歸使用中序遍歷訪問左子樹，然后訪問根節點，最后再遞歸使用中序遍歷訪問右子樹 左子樹->根節點->右子樹 ~~~ def inorder(self, root): """遞歸實現中序遍歷""" if root == None: return self.inorder(root.lchild) print root.elem self.inorder(root.rchild) ~~~ 3.后序遍歷 在后序遍歷中，我們先遞歸使用后序遍歷訪問左子樹和右子樹，最后訪問根節點 左子樹->右子樹->根節點 ~~~ def postorder(self, root): """遞歸實現后續遍歷""" if root == None: return self.postorder(root.lchild) self.postorder(root.rchild) print root.elem ~~~   ## 廣度優先遍歷(層次遍歷) 從樹的root開始，從上到下從從左到右遍歷整個樹的節點 ~~~ def breadth_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) ~~~