二叉樹的遍歷
樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結(jié)點的信息的訪問摸屠，即依次對樹中每個結(jié)點訪問一次且僅訪問一次谓罗，我們把這種對所有節(jié)點的訪問稱為遍歷（traversal）。那么樹的兩種重要的遍歷模式是深度優(yōu)先遍歷和廣度優(yōu)先遍歷,深度優(yōu)先一般用遞歸季二，廣度優(yōu)先一般用隊列妥衣。一般情況下能用遞歸實現(xiàn)的算法大部分也能用堆棧來實現(xiàn)。
深度優(yōu)先遍歷
對于一顆二叉樹戒傻，深度優(yōu)先搜索(Depth First Search)是沿著樹的深度遍歷樹的節(jié)點税手，盡可能深的搜索樹的分支。
那么深度遍歷有重要的三種方法需纳。這三種方式常被用于訪問樹的節(jié)點芦倒，它們之間的不同在于訪問每個節(jié)點的次序不同。這三種遍歷分別叫做先序遍歷（preorder）不翩，中序遍歷（inorder）和后序遍歷（postorder）兵扬。我們來給出它們的詳細定義，然后舉例看看它們的應(yīng)用口蝠。
-
先序遍歷 在先序遍歷中器钟，我們先訪問根節(jié)點，然后遞歸使用先序遍歷訪問左子樹妙蔗，再遞歸使用先序遍歷訪問右子樹
根節(jié)點->左子樹->右子樹def preorder(self, root): """遞歸實現(xiàn)先序遍歷""" if root == None: return print root.elem self.preorder(root.lchild) self.preorder(root.rchild) -
中序遍歷 在中序遍歷中傲霸，我們遞歸使用中序遍歷訪問左子樹，然后訪問根節(jié)點眉反，最后再遞歸使用中序遍歷訪問右子樹
左子樹->根節(jié)點->右子樹def inorder(self, root): """遞歸實現(xiàn)中序遍歷""" if root == None: return self.inorder(root.lchild) print root.elem self.inorder(root.rchild) -
后序遍歷 在后序遍歷中昙啄，我們先遞歸使用后序遍歷訪問左子樹和右子樹，最后訪問根節(jié)點
左子樹->右子樹->根節(jié)點def postorder(self, root): """遞歸實現(xiàn)后續(xù)遍歷""" if root == None: return self.postorder(root.lchild) self.postorder(root.rchild) print root.elem
課堂練習： 按照如圖樹的結(jié)構(gòu)寫出三種遍歷的順序:
結(jié)果：
先序:a b c d e f g h
中序:b d c e a f h g
后序:d e c b h g f a
思考：哪兩種遍歷方式能夠唯一的確定一顆樹寸五？梳凛？？
廣度優(yōu)先遍歷(層次遍歷)
從樹的root開始梳杏，從上到下從從左到右遍歷整個樹的節(jié)點
def breadth_travel(self, root):
"""利用隊列實現(xiàn)樹的層次遍歷"""
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)
