Có 2 nhóm thuật toán chính để ghé thăm toàn bộ các nút trên cây:

1. Duyệt theo chiều sâu (Depth-First Search - DFS)

Duyệt sâu xuống từng nhánh cho đến tận cùng nút lá trước khi quay lui (sử dụng Đệ quy hoặc Stack).

• In-Order (Trái - Gốc - Phải): Rất đặc biệt trên BST, kết quả duyệt sẽ trả về dãy số đã được sắp xếp tăng dần.

• Pre-Order (Gốc - Trái - Phải): Thường dùng để sao chép hoặc đóng gói (serialize) cấu trúc cây.

• Post-Order (Trái - Phải - Gốc): Thường dùng cho thao tác giải phóng bộ nhớ hoặc tính kích thước thư mục từ dưới lên.

2. Duyệt theo chiều rộng (Breadth-First Search - BFS / Level-Order)

Duyệt lần lượt từng tầng (Level) từ trên xuống dưới, từ trái sang phải (sử dụng Queue).

MÃ NGUỒN CÀI ĐẶT CÂY TÌM KIẾM NHỊ PHÂN (BST) BẰNG PYTHON

class Node:

    def __init__(self, key):
        self.val = key
        self.left = None
        self.right = None


class BinarySearchTree:

    def __init__(self):
        self.root = None

    # Thêm giá trị vào BST - O(log N)
    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert_recursive(self.root, key)

    def _insert_recursive(self, current_node, key):
        if key < current_node.val:
            if current_node.left is None:
                current_node.left = Node(key)
            else:
                self._insert_recursive(current_node.left, key)
        elif key > current_node.val:
            if current_node.right is None:
                current_node.right = Node(key)
            else:
                self._insert_recursive(current_node.right, key)

    # Tìm kiếm giá trị - O(log N)
    def search(self, key) -> bool:
        return self._search_recursive(self.root, key)

    def _search_recursive(self, current_node, key) -> bool:
        if current_node is None:
            return False
        if current_node.val == key:
            return True

        if key < current_node.val:
            return self._search_recursive(current_node.left, key)
        return self._search_recursive(current_node.right, key)

    # Duyệt cây In-Order (Trái -> Gốc -> Phải) -> Trả về danh sách tăng dần
    def inorder_traversal(self):
        result = []
        self._inorder_recursive(self.root, result)
        return result

    def _inorder_recursive(self, current_node, result):
        if current_node:
            self._inorder_recursive(current_node.left, result)  # Trái
            result.append(current_node.val)  # Gốc
            self._inorder_recursive(current_node.right, result)  # Phải


# Demo vận hành BST
bst = BinarySearchTree()
elements = [50, 30, 70, 20, 40, 60, 80]
for el in elements:
    bst.insert(el)

print("Duyệt cây In-Order (xếp tăng dần):", bst.inorder_traversal())
# Output: [20, 30, 40, 50, 60, 70, 80]

print("Tìm kiếm giá trị 40:", bst.search(40))  # Output: True
print("Tìm kiếm giá trị 99:", bst.search(99))  # Output: False

BÀI TẬP CỦNG CỐ CHƯƠNG 5

Bài tập 1: Phân tích Ứng dụng Thực tế

Trong hệ thống quản lý thư mục tập tin (File System) của một hệ điều hành (như Windows / Linux):

1. Tại sao mô hình Cây (Tree) lại là lựa chọn duy nhất đúng đắn để cấu trúc các thư mục và tập tin?

2. Khi anh muốn tính tổng dung lượng (Byte) của thư mục mẹ bao gồm toàn bộ các thư mục con bên trong, thuật toán duyệt cây nào (Pre-Order, In-Order, hay Post-Order) là phù hợp nhất? Vì sao?

Bài tập 2: Thử thách Cài đặt Thuật toán (Thực hành Code)

Viết hàm max_depth(root: Node) -> int bằng ngôn ngữ Python để tính chiều cao (độ sâu tối đa) của một Cây nhị phân.

Gợi ý: Sử dụng tư duy đệ quy: Chiều cao của một nút = $1 + \max(\text{Chiều cao cây con trái}, \text{Chiều cao cây con phải})$.

          [50]
         /    \          --> Chiều cao cây = 3
      [30]    [70]
      /
   [20]