在Python中,可以通過遞歸或者棧來實現樹的深度優先搜索,通過隊列來實現樹的廣度優先搜索。
首先,定義一個TreeNode類表示樹節點:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
接下來,定義一個函數來實現深度優先搜索:
def dfs(node):
if node is None:
return
print(node.value)
dfs(node.left)
dfs(node.right)
定義一個函數來實現廣度優先搜索:
from collections import deque
def bfs(node):
if node is None:
return
queue = deque()
queue.append(node)
while queue:
current = queue.popleft()
print(current.value)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
接下來,創建一個二叉樹并測試深度優先搜索和廣度優先搜索:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print("深度優先搜索:")
dfs(root)
print("\n廣度優先搜索:")
bfs(root)
以上代碼演示了如何實現樹的深度優先搜索和廣度優先搜索。深度優先搜索會先遍歷完整的左子樹,然后再遍歷右子樹,而廣度優先搜索會先遍歷同一層的所有節點,再遍歷下一層的節點。