Bài toánn cơ bản về Cây trong lập trình

 

I. LÝ THUYẾT CƠ BẢN VỀ CÂY
1. Cây là gì?
Cây là một cấu trúc dữ liệu dùng để lưu trữ dữ liệu có dạng phân cấp (giống như sơ đồ tổ chức, cây gia phả,...)
- Mỗi nút (node) trong cây có thể kết nối với nhiều nút con, nhưng chỉ có một nút cha.
- Có một nút đặc biệt gọi là "gốc" (root) — là nơi bắt đầu của cây.
Ví dụ minh họa cây đơn giản:

       A           ← Đây là nút gốc

      / \

     B   C         ← B và C là con của A

    / \

   D   E           ← D và E là con của B

2. Các thuật ngữ cơ bản
Node (Nút): Là một phần tử trong cây (như A, B, C, D, E)
Root (Gốc): Là nút đầu tiên, không có cha (như A ở trên)
Child (Con): Là nút nằm dưới một nút khác (B là con của A)
Parent (Cha): Là nút nằm trên, có nút con (A là cha của B)
Leaf (Lá): Là nút không có con (D, E, C là các nút lá)
Depth (Độ sâu): Là khoảng cách từ gốc đến nút đó (gốc có depth 0)
II. CÀI ĐẶT CÂY CƠ BẢN TRONG PYTHON
1. Tạo lớp Node (Nút)

2. Ví dụ tạo cây như hình minh họa:

Cây này tương đương hình sau:

        A

      /   \

     B     C

    / \

   D   E

 III. DUYỆT CÂY (Traversal)
1. Duyệt theo chiều sâu (DFS - Depth First Search)

 Kết quả:

A

  B

    D

    E

  C

Giải thích:
- In A (gốc)
- Vào B → in B → rồi D → rồi E
- Quay lại lên → sang C → in C
IV. VÍ DỤ BÀI TOÁN THỰC TẾ
1. Ví dụ: Đếm số nút trong cây

Kết quả: Số nút trong cây: 5

Giải thích: Gồm các nút A, B, C, D, E → tổng cộng 5 nút.
Ví dụ: Đếm số lá (nút không có con)


Kết quả: Số nút lá: 3 (gồm C, D, E)
V. KẾT LUẬN
- Cây là cấu trúc rất quan trọng giúp lưu trữ dữ liệu phân cấp
- Mỗi nút có thể có nhiều con nhưng chỉ có 1 cha
- Duyệt cây là kỹ thuật cơ bản giúp giải các bài toán như:
+ Đếm nút
+ Tìm kiếm
+ Tính chiều cao cây
VI. BÀI TẬP LUYỆN TẬP

Bài tập 1. Viết hàm đếm chiều cao cây
Yêu cầu: Tính chiều cao của cây, tức là độ sâu lớn nhất từ nút gốc đến một nút lá.
Giải thích: 
+ Nếu cây chỉ có một nút (gốc), chiều cao là 1
+ Nếu có nhiều lớp con, thì ta tính chiều cao của các nhánh, rồi lấy nhánh cao nhất.

Ý tưởng:

- Nếu không có con → chiều cao = 1
- Nếu có con → chiều cao = 1 + chiều cao lớn nhất của các con
Code

BÀI TẬP 2: Viết hàm tìm một giá trị trong cây
Yêu cầu: Viết hàm kiểm tra xem một giá trị có tồn tại trong cây hay không.
Giải thích: 
- Duyệt toàn bộ cây (DFS).
- Nếu thấy nút có data đúng thì trả về True
- Nếu duyệt hết mà không thấy thì trả về False
Ý tưởng:
- So sánh giá trị tại nút hiện tại.
- Nếu khác → duyệt tiếp các con (đệ quy)
Code:


BÀI TẬP 3: In cây theo thứ tự duyệt trước (DFS)
Yêu cầu: Viết hàm in tên các nút theo thứ tự duyệt trước (Duyệt từ gốc trước, sau đó duyệt các con từ trái sang phải).
Ý tưởng: 
- In nút hiện tại trước (gốc).
- Sau đó đệ quy duyệt từng con.

TỔNG KẾT
- Đếm chiều cao cây: Kỹ thuật chính: Đệ quy + max()    Mục tiêu: Đệ quy + max()
- Tìm giá trị trong cây:  Kỹ thuật chính: Đệ quy + so sánh    Mục tiêu:Kiểm tra dữ liệu
- In cây duyệt trước: Kỹ thuật chính: DFS (Depth-First)    Mục tiêu: Nắm thứ tự duyệt

Bài toán đệ quy

I. Đệ quy là gì?

        Đệ quy là kỹ thuật trong lập trình mà trong đó một hàm gọi lại chính nó để giải quyết một bài toán.

    Giải pháp đệ quy chia bài toán lớn thành các bài toán con giống chính nó, nhưng nhỏ hơn → cho đến khi đạt được “điều kiện dừng” (base case).

II. Cấu trúc của một hàm đệ quy

    1. Điều kiện dừng (base case) – để kết thúc đệ quy, tránh lặp vô hạn.

    2. Gọi lại chính nó (recursive call) – để giải bài toán con.

python

    def  ham_de_quy():

        if điều_kiện_dừng:

        return kết_quả

        else:

        return ham_de_quy(giá_trị_mới)

III. Ví dụ dễ hiểu: Tính giai thừa

Định nghĩa toán học:

$$n! = n \times (n-1) \times (n-2) \times \dots \times 1 \quad (n > 0), \quad 0! = 1$$

Viết bằng Python:

 Giải thích: 

- giaithua(3)` sẽ tính như sau: 

3 * giaithua(2) * 3* (2 * giaithua(1)) * 3 * (2 * (1 * giaithua(0))) *`3 * 2 * 1 * 1 = 6

IV. Ví dụ 2: Tính dãy Fibonacci

$$ F(0) = 0,\quad F(1) = 1,\quad F(n) = F(n-1) + F(n-2) $$ Ví dụ 3: Tính tổng từ 1 đến n Giải thích: t

        Tong(4) = 4 + tong(3) = 4 + 3 + tong(2) = 4 + 3 + 2 + 1 = 10

VI. Khi nào dùng đệ quy? Đệ quy phù hợp khi:

     * Bài toán có thể chia thành các bài toán con giống nhau 

     * Cần giải bài toán cây, danh sách lồng nhau, thuật toán chia để trị (ví dụ: quicksort, mergesort) 

VII. Cảnh báo khi dùng đệ quy 

        Đệ quy có thể gây tràn bộ nhớ (stack overflow) nếu không có điều kiện dừng. 

        Với bài toán lớn, đệ quy chạy chậm hơn vòng lặp → cần cải tiến như memoization hoặc quy hoạch động (dynamic programming).

Thuật toán tìm kiếm trong lập trình

🧠 CHIA SẺ VỀ THUẬT TOÁN TÌM KIẾM TRONG LẬP TRÌNH
🎯 1. Mục tiêu bài học
Hiểu khái niệm thuật toán tìm kiếm là gì.
Biết được 2 thuật toán tìm kiếm cơ bản: Tìm kiếm tuyến tính (Linear Search) và Tìm kiếm nhị phân (Binary Search).
Vận dụng lập trình Python để cài đặt các thuật toán này.
Thực hành giải bài toán sử dụng thuật toán tìm kiếm.
📚 2. Lý thuyết cơ bản
🔍 2.1. Tìm kiếm là gì?
Tìm kiếm là quá trình tìm một phần tử có giá trị thỏa mãn điều kiện nào đó trong một tập hợp (danh sách, mảng,...).
🔁 2.2. Thuật toán Tìm kiếm tuyến tính (Linear Search)
Tìm từng phần tử trong danh sách, từ đầu đến cuối.
Phù hợp với danh sách chưa sắp xếp.
✅ Ưu điểm: Đơn giản, dễ cài đặt.
❌ Nhược điểm: Tốc độ chậm khi danh sách lớn (O(n)).
🧩 Ví dụ minh hoạ:

🧮 2.3. Thuật toán Tìm kiếm nhị phân (Binary Search) Áp dụng với danh sách đã sắp xếp. Chia đôi danh sách, so sánh với phần tử ở giữa. ✅ Ưu điểm: Rất nhanh, độ phức tạp O(log n). ❌ Nhược điểm: Phải sắp xếp trước. 🧩 Ví dụ minh hoạ: ▶️ Giải thích chi tiết ví dụ: left là chỉ số đầu danh sách, right là cuối. mid là phần tử giữa, so sánh arr[mid] với x: Nếu bằng → tìm thấy. Nếu nhỏ hơn → bỏ qua nửa trái. Nếu lớn hơn → bỏ qua nửa phải. 🧪 Thử nghiệm: 🎓 3. Bài tập có lời giải chi tiết 🧠 Bài 1: Tìm kiếm số lẻ đầu tiên trong danh sách Yêu cầu: Viết hàm tìm số lẻ đầu tiên trong danh sách. Lời giải: ✅ Giải thích: Duyệt từng phần tử, kiểm tra nếu là số lẻ (% 2 == 1) thì trả về. 🧪 Thử: 🧠 Bài 2: Kiểm tra một số có tồn tại trong danh sách đã sắp xếp chưa? Yêu cầu: Viết hàm kiểm tra số x có trong danh sách sắp xếp chưa? Lời giải: ✅ Giải thích: Dùng lại binary_search, nếu trả về khác -1 nghĩa là có tồn tại. 🧪 Thử: 🧠 Bài 3: Đếm số lần xuất hiện của phần tử x trong danh sách ✅ Giải thích: Duyệt danh sách, nếu phần tử bằng x thì tăng biến đếm. 🧪 Thử: 📌 4. Tổng kết Thuật toán Dùng khi Tốc độ Độ phức tạp Linear Search Danh sách chưa sắp xếp Chậm O(n) Binary Search Danh sách đã sắp xếp Rất nhanh O(log n)

▶️ Giải thích chi tiết ví dụ:

arr là danh sách các phần tử.

x là giá trị cần tìm.

Duyệt từng phần tử, nếu phần tử bằng x thì trả về vị trí i.

Nếu duyệt xong mà không thấy thì trả về -1.

🧪 Thử nghiệm: