Duyệt cây nhị phân là một thao tác cơ bản và quan trọng trong khoa học máy tính, cho phép chúng ta truy cập từng nút trong cây theo một thứ tự xác định. Bài viết này sẽ đi sâu vào các kỹ thuật duyệt cây nhị phân, bao gồm duyệt theo chiều sâu (DFS) và duyệt theo chiều rộng (BFS), cùng với các phương pháp cài đặt khác nhau.
Các Khái Niệm Cơ Bản Về Cây Nhị Phân
Phân loại Cây Nhị Phân
- Cây Nhị Phân Đầy Đủ (Full Binary Tree): Một cây nhị phân được gọi là đầy đủ nếu mỗi nút có 0 hoặc 2 con. Tất cả các nút lá nằm ở cùng một độ sâu. Một cây đầy đủ có độ sâu k sẽ có chính xác 2^k - 1 nút.
- Cây Nhị Phân Hoàn Chỉnh (Complete Binary Tree): Trong cây nhị phân hoàn chỉnh, tất cả các cấp độ đều được lấp đầy, trừ có thể cấp độ cuối cùng. Các nút ở cấp độ cuối cùng phải được lấp đầy từ trái sang phải.
- Cây Tìm Kiếm Nhị Phân (Binary Search Tree - BST): Là một cây nhị phân có thứ tự. Đối với mỗi nút, tất cả các nút trong cây con bên trái của nó có giá trị nhỏ hơn nút đó, và tất cả các nút trong cây con bên phải của nó có giá trị lớn hơn nút đó. Cây con trái và phải của mỗi nút cũng phải là cây tìm kiếm nhị phân.
- Cây Tìm Kiếm Nhị Phân Cân Bằng (Balanced Binary Search Tree - AVL Tree): Là một BST mà sự khác biệt về chiều cao giữa cây con bên trái và cây con bên phải của bất kỳ nút nào không vượt quá 1. Cả cây con bên trái và bên phải cũng phải là cây AVL.
Phương Thức Lưu Trữ Cây Nhị Phân
- Lưu trữ dạng liên kết: Mỗi nút chứa giá trị, con trỏ đến nút con trái và con trỏ đến nút con phải. Đây là cách lưu trữ phổ biến nhất cho cây nhị phân.
- Lưu trữ dạng mảng (tuần tự): Các nút được lưu trữ trong một mảng. Nếu một nút có chỉ số `i` trong mảng (bắt đầu từ 0), thì nút con trái của nó sẽ ở chỉ số `2 * i + 1`, và nút con phải ở chỉ số `2 * i + 2`.
Các Phương Thức Duyệt Cây Nhị Phân
Có hai nhóm phương pháp duyệt chính:
- Duyệt theo chiều sâu (Depth-First Search - DFS):
- Duyệt tiền thứ tự (Pre-order Traversal)
- Duyệt trung thứ tự (In-order Traversal)
- Duyệt hậu thứ tự (Post-order Traversal)
- Duyệt theo chiều rộng (Breadth-First Search - BFS):
- Duyệt theo cấp độ (Level-order Traversal)
Thứ tự của nút gốc (trung tâm) trong quá trình duyệt sẽ định nghĩa loại duyệt:
- Tiền thứ tự (Gốc - Trái - Phải): Đầu tiên xử lý nút gốc, sau đó đệ quy duyệt cây con bên trái, và cuối cùng đệ quy duyệt cây con bên phải.
- Trung thứ tự (Trái - Gốc - Phải): Đầu tiên đệ quy duyệt cây con bên trái, sau đó xử lý nút gốc, và cuối cùng đệ quy duyệt cây con bên phải.
- Hậu thứ tự (Trái - Phải - Gốc): Đầu tiên đệ quy duyệt cây con bên trái, sau đó đệ quy duyệt cây con bên phải, và cuối cùng xử lý nút gốc.
Định Nghĩa Nút Cây Nhị Phân
Đây là cấu trúc lớp cơ bản cho một nút trong cây nhị phân, được sử dụng trong các ví dụ code dưới đây:
class TreeNode:
def __init__(self, value=0, left_child=None, right_child=None):
self.value = value
self.left = left_child
self.right = right_child
Duyệt Cây Nhị Phân Bằng Đệ Quy
Cài đặt duyệt cây bằng đệ quy thường tuân theo ba bước chính:
- Xác định tham số và giá trị trả về của hàm đệ quy: Quyết định những tham số nào cần thiết cho quá trình đệ quy và kiểu trả về của hàm.
- Xác định điều kiện dừng: Điều kiện này rất quan trọng để tránh lỗi tràn ngăn xếp (stack overflow). Hàm đệ quy phải có một điểm dừng rõ ràng.
- Xác định logic cho một tầng đệ quy: Xác định công việc cần thực hiện tại mỗi cấp độ đệ quy và cách hàm gọi chính nó để tiếp tục quá trình.
1. Duyệt Tiền Thứ Tự (Pre-order Traversal) - Đệ Quy
Thứ tự: Gốc - Trái - Phải.
from typing import Optional, List
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
collected_values = [] # Danh sách lưu trữ kết quả duyệt
def visit_node_recursive(current_node: Optional[TreeNode]):
# Điều kiện dừng: nếu nút hiện tại là None, không làm gì cả
if current_node is None:
return
# Thao tác "Gốc": Thêm giá trị của nút hiện tại vào danh sách
collected_values.append(current_node.value)
# Thao tác "Trái": Duyệt cây con bên trái
visit_node_recursive(current_node.left)
# Thao tác "Phải": Duyệt cây con bên phải
visit_node_recursive(current_node.right)
# Bắt đầu duyệt từ nút gốc
visit_node_recursive(root)
return collected_values
2. Duyệt Trung Thứ Tự (In-order Traversal) - Đệ Quy
Thứ tự: Trái - Gốc - Phải.
from typing import Optional, List
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
collected_values = []
def visit_node_recursive(current_node: Optional[TreeNode]):
if current_node is None:
return
# Thao tác "Trái"
visit_node_recursive(current_node.left)
# Thao tác "Gốc"
collected_values.append(current_node.value)
# Thao tác "Phải"
visit_node_recursive(current_node.right)
visit_node_recursive(root)
return collected_values
3. Duyệt Hậu Thứ Tự (Post-order Traversal) - Đệ Quy
Thứ tự: Trái - Phải - Gốc.
from typing import Optional, List
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
collected_values = []
def visit_node_recursive(current_node: Optional[TreeNode]):
if current_node is None:
return
# Thao tác "Trái"
visit_node_recursive(current_node.left)
# Thao tác "Phải"
visit_node_recursive(current_node.right)
# Thao tác "Gốc"
collected_values.append(current_node.value)
visit_node_recursive(root)
return collected_values
Duyệt Cây Nhị Phân Bằng Lặp (Iterative Traversal)
Duyệt lặp thường sử dụng một cấu trúc dữ liệu phụ trợ, như ngăn xếp (stack), để mô phỏng quá trình đệ quy.
1. Duyệt Tiền Thứ Tự (Pre-order Traversal) - Lặp
Để duyệt tiền thứ tự (Gốc-Trái-Phải) bằng ngăn xếp, chúng ta thêm nút gốc vào ngăn xếp trước. Khi lấy một nút ra khỏi ngăn xếp, ta thêm giá trị của nó vào kết quả. Sau đó, ta đẩy con phải của nó vào ngăn xếp (để xử lý sau) rồi đẩy con trái của nó vào ngăn xếp (để xử lý trước).
from typing import Optional, List
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
processing_stack = [root] # Ngăn xếp chứa các nút cần xử lý
output_sequence = [] # Danh sách lưu trữ kết quả duyệt
while processing_stack:
current_node = processing_stack.pop() # Lấy nút trên cùng ra
output_sequence.append(current_node.value) # Ghi nhận giá trị (Gốc)
# Đẩy con phải vào trước, để nó được xử lý SAU con trái
if current_node.right:
processing_stack.append(current_node.right)
# Đẩy con trái vào sau, để nó được xử lý TRƯỚC con phải
if current_node.left:
processing_stack.append(current_node.left)
return output_sequence
2. Duyệt Trung Thứ Tự (In-order Traversal) - Lặp
Duyệt trung thứ tự (Trái-Gốc-Phải) phức tạp hơn một chút với phương pháp lặp. Chúng ta cần một con trỏ để di chuyển xuống nhánh trái sâu nhất và một ngăn xếp để lưu trữ các nút gốc tiềm năng khi chúng ta đi xuống.
from typing import Optional, List
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
collected_values = [] # Danh sách lưu trữ các giá trị đã duyệt
exploration_stack = [] # Ngăn xếp để lưu trữ các nút cha tiềm năng
current_node_ptr = root # Con trỏ để di chuyển xuống cây
while current_node_ptr or exploration_stack:
# Di chuyển xuống nhánh trái sâu nhất, đẩy tất cả các nút trên đường đi vào stack
while current_node_ptr:
exploration_stack.append(current_node_ptr)
current_node_ptr = current_node_ptr.left
# Khi đã xuống sâu nhất bên trái, lấy nút từ stack ra
current_node_ptr = exploration_stack.pop()
collected_values.append(current_node_ptr.value) # Xử lý nút (Gốc)
# Chuyển sang cây con bên phải để xử lý
current_node_ptr = current_node_ptr.right
return collected_values
3. Duyệt Hậu Thứ Tự (Post-order Traversal) - Lặp
Một cách phổ biến để cài đặt duyệt hậu thứ tự (Trái-Phải-Gốc) bằng lặp là sử dụng một biến thể của duyệt tiền thứ tự. Duyệt tiền thứ tự theo thứ tự Gốc-Phải-Trái, sau đó đảo ngược kết quả sẽ cho thứ tự Trái-Phải-Gốc.
from typing import Optional, List
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
processing_stack = [root] # Ngăn xếp cho duyệt Gốc-Phải-Trái
temp_result = [] # Danh sách tạm thời lưu kết quả Gốc-Phải-Trái
while processing_stack:
current_node = processing_stack.pop()
temp_result.append(current_node.value) # Ghi nhận giá trị (Gốc)
# Đẩy con trái vào trước, để nó được xử lý SAU con phải
if current_node.left:
processing_stack.append(current_node.left)
# Đẩy con phải vào sau, để nó được xử lý TRƯỚC con trái
if current_node.right:
processing_stack.append(current_node.right)
# Đảo ngược danh sách để có thứ tự Trái-Phải-Gốc
return temp_result[::-1]
Duyệt Cây Nhị Phân Bằng Lặp "Thống Nhất"
Các phương pháp lặp trên thường đòi hỏi logic khác nhau cho mỗi loại duyệt do sự khác biệt về thời điểm "truy cập" nút và thời điểm "xử lý" (thêm vào kết quả) nút. Phương pháp "thống nhất" cố gắng giải quyết vấn đề này bằng cách sử dụng một đánh dấu đặc biệt (ví dụ: `None`) để phân biệt giữa các nút cần được truy cập lại và các nút đã sẵn sàng để xử lý.
Khi một nút được đẩy vào ngăn xếp, ta cũng đẩy một đánh dấu (ví dụ: `None`) theo sau nó. Khi rút một mục ra khỏi ngăn xếp:
- Nếu đó là đánh dấu (`None`), thì mục tiếp theo trong ngăn xếp chính là nút cần xử lý (vì nó đã được thăm dò các con).
- Nếu đó là một nút, ta đẩy các con của nó (theo thứ tự ngược lại của loại duyệt) và sau đó đẩy nút đó trở lại cùng với đánh dấu của nó.
1. Duyệt Tiền Thứ Tự (Pre-order Traversal) - Lặp Thống Nhất
Thứ tự xử lý: Gốc - Trái - Phải. Khi gặp nút, đẩy Gốc (cùng dấu), sau đó đẩy Phải, Trái.
from typing import Optional, List
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
final_output = []
traversal_stack = []
if root:
traversal_stack.append(root)
while traversal_stack:
current_item = traversal_stack.pop()
if current_item is not None:
# Đẩy nút trở lại cùng với một đánh dấu (None)
# để biết khi nào nó đã sẵn sàng được xử lý (Gốc)
# Quan trọng: Đẩy theo thứ tự ngược lại của duyệt Gốc-Trái-Phải
# để đảm bảo đúng thứ tự khi pop
if current_item.right: # Phải
traversal_stack.append(current_item.right)
if current_item.left: # Trái
traversal_stack.append(current_item.left)
traversal_stack.append(current_item) # Gốc (để xử lý sau)
traversal_stack.append(None) # Đánh dấu
else: # Nếu gặp đánh dấu None, thì mục tiếp theo là nút cần xử lý
actual_node = traversal_stack.pop()
final_output.append(actual_node.value)
return final_output
2. Duyệt Trung Thứ Tự (In-order Traversal) - Lặp Thống Nhất
Thứ tự xử lý: Trái - Gốc - Phải. Khi gặp nút, đẩy Phải, Gốc (cùng dấu), Trái.
from typing import Optional, List
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
final_output = []
traversal_stack = []
if root:
traversal_stack.append(root)
while traversal_stack:
current_item = traversal_stack.pop()
if current_item is not None:
# Đẩy theo thứ tự ngược lại của duyệt Trái-Gốc-Phải
if current_item.right: # Phải
traversal_stack.append(current_item.right)
traversal_stack.append(current_item) # Gốc (để xử lý sau)
traversal_stack.append(None) # Đánh dấu
if current_item.left: # Trái
traversal_stack.append(current_item.left)
else:
actual_node = traversal_stack.pop()
final_output.append(actual_node.value)
return final_output
3. Duyệt Hậu Thứ Tự (Post-order Traversal) - Lặp Thống Nhất
Thứ tự xử lý: Trái - Phải - Gốc. Khi gặp nút, đẩy Gốc (cùng dấu), Phải, Trái.
from typing import Optional, List
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
final_output = []
traversal_stack = []
if root:
traversal_stack.append(root)
while traversal_stack:
current_item = traversal_stack.pop()
if current_item is not None:
# Đẩy theo thứ tự ngược lại của duyệt Trái-Phải-Gốc
traversal_stack.append(current_item) # Gốc (để xử lý sau)
traversal_stack.append(None) # Đánh dấu
if current_item.right: # Phải
traversal_stack.append(current_item.right)
if current_item.left: # Trái
traversal_stack.append(current_item.left)
else:
actual_node = traversal_stack.pop()
final_output.append(actual_node.value)
return final_output
Duyệt Cây Nhị Phân Theo Cấp Độ (Level-order Traversal)
Duyệt theo cấp độ là một dạng của duyệt theo chiều rộng (BFS). Nó duyệt cây từng cấp một, từ trái sang phải. Cấu trúc dữ liệu thích hợp nhất cho duyệt cấp độ là hàng đợi (queue), vì tính chất "vào trước ra trước" (FIFO) của nó phù hợp với logic duyệt từng tầng.
1. Duyệt Cấp Độ Chuẩn (Level-order Traversal)
a. Duyệt Cấp Độ - Đệ Quy
Mặc dù duyệt cấp độ thường được cài đặt bằng lặp và hàng đợi, nhưng nó cũng có thể được thực hiện bằng đệ quy, bằng cách truyền cấp độ hiện tại xuống các hàm gọi đệ quy.
from typing import Optional, List
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
results_by_level = [] # Danh sách của các danh sách, mỗi danh sách con là một cấp độ
def collect_nodes_at_level(node: Optional[TreeNode], current_level: int):
if not node:
return
# Nếu đây là cấp độ mới, tạo một danh sách con mới cho nó
if len(results_by_level) == current_level:
results_by_level.append([])
# Thêm giá trị của nút hiện tại vào danh sách của cấp độ tương ứng
results_by_level[current_level].append(node.value)
# Đệ quy cho các nút con, tăng cấp độ lên 1
collect_nodes_at_level(node.left, current_level + 1)
collect_nodes_at_level(node.right, current_level + 1)
# Bắt đầu đệ quy từ nút gốc, cấp độ ban đầu là 0
collect_nodes_at_level(root, 0)
return results_by_level
b. Duyệt Cấp Độ - Dùng Hai Mảng
Phương pháp này sử dụng hai mảng (hoặc danh sách trong Python) để quản lý các nút ở cấp độ hiện tại và cấp độ tiếp theo.
from typing import Optional, List
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
all_levels_data = [] # Lưu trữ kết quả cuối cùng (các cấp độ)
current_level_nodes = [root] # Các nút ở cấp độ hiện tại
while current_level_nodes:
next_level_nodes = [] # Các nút sẽ thuộc cấp độ tiếp theo
current_level_values = [] # Giá trị của các nút ở cấp độ hiện tại
for node in current_level_nodes:
current_level_values.append(node.value)
# Thêm các nút con vào danh sách cho cấp độ tiếp theo
if node.left:
next_level_nodes.append(node.left)
if node.right:
next_level_nodes.append(node.right)
all_levels_data.append(current_level_values)
current_level_nodes = next_level_nodes # Cập nhật cho vòng lặp tiếp theo
return all_levels_data
c. Duyệt Cấp Độ - Dùng Một Hàng Đợi
Đây là phương pháp phổ biến và hiệu quả nhất cho duyệt cấp độ, sử dụng `collections.deque` trong Python để tối ưu hóa thao tác hàng đợi.
import collections
from typing import Optional, List
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
results_by_level = []
node_queue = collections.deque([root]) # Khởi tạo hàng đợi với nút gốc
while node_queue:
current_level_size = len(node_queue) # Số lượng nút ở cấp độ hiện tại
level_values_list = [] # Danh sách giá trị cho cấp độ hiện tại
# Duyệt qua tất cả các nút ở cấp độ hiện tại
for _ in range(current_level_size):
current_node = node_queue.popleft() # Lấy nút đầu tiên ra
level_values_list.append(current_node.value)
# Thêm các nút con vào cuối hàng đợi cho cấp độ tiếp theo
if current_node.left:
node_queue.append(current_node.left)
if current_node.right:
node_queue.append(current_node.right)
results_by_level.append(level_values_list)
return results_by_level
2. Duyệt Cấp Độ Ngược (Level-order Traversal II - Bottom-up)
Duyệt cấp độ từ dưới lên chỉ đơn giản là thực hiện duyệt cấp độ chuẩn, sau đó đảo ngược thứ tự của các danh sách cấp độ đã thu thập.
a. Dùng Hai Mảng (Ngược)
from typing import Optional, List
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
all_levels_data = []
current_level_nodes = [root]
while current_level_nodes:
next_level_nodes = []
current_level_values = []
for node in current_level_nodes:
current_level_values.append(node.value)
if node.left:
next_level_nodes.append(node.left)
if node.right:
next_level_nodes.append(node.right)
all_levels_data.append(current_level_values)
current_level_nodes = next_level_nodes
return all_levels_data[::-1] # Đảo ngược danh sách cuối cùng
b. Dùng Một Hàng Đợi (Ngược)
import collections
from typing import Optional, List
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
results_by_level = []
node_queue = collections.deque([root])
while node_queue:
current_level_size = len(node_queue)
level_values_list = []
for _ in range(current_level_size):
current_node = node_queue.popleft()
level_values_list.append(current_node.value)
if current_node.left:
node_queue.append(current_node.left)
if current_node.right:
node_queue.append(current_node.right)
results_by_level.append(level_values_list)
return results_by_level[::-1] # Đảo ngược danh sách cuối cùng
3. Duyệt Cấp Độ Cây N-ary (N-ary Tree Level Order Traversal)
Cây N-ary là cây mà mỗi nút có thể có nhiều hơn hai con. Logic duyệt cấp độ vẫn tương tự như cây nhị phân, chỉ khác ở cách truy cập các nút con (thường là một danh sách các nút con).
Định nghĩa nút cho cây N-ary:
class NaryNode:
def __init__(self, val: Optional[int] = None, children: Optional[List['NaryNode']] = None):
self.val = val
self.children = children if children is not None else []
a. Dùng Hai Mảng (Cây N-ary)
from typing import Optional, List
# Định nghĩa NaryNode như trên
class Solution:
def levelOrder(self, root: 'NaryNode') -> List[List[int]]:
if root is None:
return []
all_level_data = []
current_level_nodes = [root]
while current_level_nodes:
current_level_values = []
next_level_nodes = []
for node in current_level_nodes:
current_level_values.append(node.val)
# Mở rộng danh sách các nút con cho cấp độ tiếp theo
if node.children: # Chỉ thêm nếu có con
next_level_nodes.extend(node.children)
all_level_data.append(current_level_values)
current_level_nodes = next_level_nodes
return all_level_data
b. Dùng Một Hàng Đợi (Cây N-ary)
import collections
from typing import Optional, List
# Định nghĩa NaryNode như trên
class Solution:
def levelOrder(self, root: 'NaryNode') -> List[List[int]]:
if root is None:
return []
results_output = []
node_queue = collections.deque([root])
while node_queue:
current_level_count = len(node_queue)
level_items = []
for _ in range(current_level_count):
node_to_process = node_queue.popleft()
level_items.append(node_to_process.val)
# Thêm tất cả các con của nút hiện tại vào hàng đợi
if node_to_process.children:
node_queue.extend(node_to_process.children)
results_output.append(level_items)
return results_output