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