二叉樹遍歷
樹的遍歷是樹的一種重要的運算伐坏。所謂遍歷是指對樹中所有結(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)
這里寫圖片描述
廣度優(yōu)先遍歷(層次遍歷)
從樹的root開始粟瞬，從上到下從從左到右遍歷整個樹的節(jié)點
def breadth_travel(self):
"""廣度優(yōu)先遍歷"""
if self.root is None:
return
else:
queue = []
queue.append(self.root)
while len(queue) > 0:
node = queue.pop(0)
print(node.item, end=" ")
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
完整代碼
class Node(object):
"""節(jié)點"""
def __init__(self, item):
self.item = item
self.lchild = None
self.rchild = None
class BinaryTree(object):
"""二叉樹"""
def __init__(self, node=None):
self.root = node
def add(self, item):
""""""
if self.root is None:
self.root = Node(item)
else:
queue = []
queue.append(self.root)
while len(queue) > 0:
node = queue.pop(0)
if not node.lchild:
node.lchild = Node(item)
return
else:
queue.append(node.lchild)
if not node.rchild:
node.rchild = Node(item)
return
else:
queue.append(node.rchild)
def breadth_travel(self):
"""廣度優(yōu)先遍歷"""
if self.root is None:
return
else:
queue = []
queue.append(self.root)
while len(queue) > 0:
node = queue.pop(0)
print(node.item, end=" ")
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
def preorder_travel(self, node):
"""根 左 右"""
if node:
print(node.item, end=" ")
self.preorder_travel(node.lchild)
self.preorder_travel(node.rchild)
else:
return
def inorder_travel(self, node):
"""左 根 右"""
if node:
self.inorder_travel(node.lchild)
print(node.item, end=" ")
self.inorder_travel(node.rchild)
else:
return
def postorder_travel(self, node):
"""左 右 根"""
if node:
self.postorder_travel(node.lchild)
self.postorder_travel(node.rchild)
print(node.item, end=" ")
else:
return
#測試
if __name__ == '__main__':
t = BinaryTree()
t.add(0)
t.add(1)
t.add(2)
t.add(3)
t.add(4)
t.add(5)
t.add(6)
t.add(7)
t.add(8)
t.add(9)
t.breadth_travel()
print("")
t.preorder_travel(t.root)
print("")
t.inorder_travel(t.root)
print("")
t.postorder_travel(t.root)
print("")
