Python樹遍歷算法
遍歷是訪問樹的所有節點的過程，也可以打印它們的值。 因爲所有節點都通過邊(鏈接)連接，所以始終從根(頭)節點開始。 也就是說，我們不能隨機訪問樹中的一個節點。 這裏介紹三種方式來遍歷一棵樹 -
- 順序遍歷
- 前序遍歷
- 後序遍歷
按順序遍歷
在這種遍歷方法中，首先訪問左側子樹，然後訪問根，然後訪問右側子樹。 我們應該永遠記住每個節點本身可能代表一個子樹。
在下面的python程序中，使用Node類爲根節點以及左右節點創建佔位符。 然後創建一個insert()函數來將數據添加到樹中。 最後，Inorder遍歷邏輯通過創建一個空列表，並首先添加添加根節點或父節點，然後左節點來實現。 最後添加左節點以完成Inorder遍歷。 請注意，對於每個子樹重複此過程，直到遍歷所有節點。
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Inorder traversal
# Left -> Root -> Right
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))執行上面示例代碼，得到以下結果 -
[10, 14, 19, 27, 31, 35, 42]前序遍歷
在這種遍歷方法中，首先訪問根節點，然後訪問左邊的子樹，最後訪問右邊的子樹。
在下面的python程序中，使用Node類爲根節點以及左右節點創建佔位符。 然後創建一個insert()函數來將數據添加到樹中。 最後，前序遍歷遍歷邏輯通過創建一個空列表並首先添加根節點，然後添加左節點來實現。 最後添加右節點以完成前序遍歷。 請注意，對於每個子樹重複此過程，直到遍歷所有節點。
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Preorder traversal
# Root -> Left ->Right
def PreorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.PreorderTraversal(root.left)
res = res + self.PreorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))當上面的代碼被執行時，它會產生以下結果 -
[27, 14, 10, 19, 35, 31, 42]後序遍歷
在這個遍歷方法中，最後訪問根節點。 首先遍歷左子樹，然後遍歷右子樹，最後遍歷根節點。
在下面的python程序中，使用Node類爲根節點以及左右節點創建佔位符。 然後創建一個insert()函數來將數據添加到樹中。 最後，通過創建一個空列表並添加左節點，然後添加右節點來實現後序遍歷邏輯。 最後，添加根或父節點以完成後序遍歷。 請注意，對於每個子樹重複此過程，直到遍歷所有節點。參考以下代碼實現 -
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))當上面的代碼被執行時，它會產生以下結果 -
[10, 19, 14, 31, 42, 35, 27]