Chuyển tới nội dung chính

Cây & cây nhị phân; cách duyệt

Bạn sẽ học được gì

Cây (tree) là cấu trúc phân cấp — như cây thư mục, cây gia phả. Bạn sẽ nắm thuật ngữ, hiểu cây nhị phân, và bốn cách duyệt cây: tiền/trung/hậu thứ tự (DFS) và theo lớp (BFS).

1. Trực quan: cấu trúc phân cấp​

Khác mảng/linked list (tuyến tính), cây phân nhánh. Mỗi nút có thể có nhiều con.

            ┌───┐
            │ 4 │  ← gốc (root)
            └─┬─┘
        ┌─────┴─────┐
      ┌─┴─┐       ┌─┴─┐
      │ 2 │       │ 6 │   ← nút trong
      └─┬─┘       └───┘
    ┌───┴───┐
  ┌─┴─┐   ┌─┴─┐
  │ 1 │   │ 3 │           ← lá (leaf, không con)
  └───┘   └───┘

Thuật ngữ: gốc (root) = nút trên cùng; cha/con (parent/child); lá (leaf) = nút không có con; độ sâu/chiều cao (depth/height). Cây không có chu trình — đi xuống là không quay lại.

2. Cây nhị phân (binary tree)​

Cây nhị phân = mỗi nút có tối đa 2 con: con trái và con phải. Đây là loại cây quan trọng nhất, nền của BST, heap, và nhiều thuật toán.

Đang tải trình chạy code…

3. Bốn cách duyệt cây​

CáchThứ tự thămDùng để
Tiền thứ tự (preorder)gốc → trái → phảisao chép cây, in cấu trúc
Trung thứ tự (inorder)trái → gốc → phảiBST cho ra dãy đã sắp xếp!
Hậu thứ tự (postorder)trái → phải → gốcxóa cây, tính từ lá lên
Theo lớp (level-order)từng tầng từ trên xuốngBFS, in theo tầng

Ba cách đầu là DFS (đi sâu, dùng đệ quy). Cách cuối là BFS (dùng queue — nhớ bài 2.3.2).

4. Chạy debug: duyệt TRUNG thứ tự (inorder)​

Inorder thăm trái → gốc → phải. Bước qua cây trên — chú ý kết quả ra 1, 2, 3, 4, 6 (đúng thứ tự tăng vì đây là cây sắp xếp):

🐞 Inorder: trái → gốc → phảiBước 1/7
1def inorder(nut):
2  if nut is None:
3      return
4  inorder(nut.trai)
5  tham(nut.val)
6  inorder(nut.phai)
Biến tại bước này
tại4
👉 Vào gốc 4, đi TRÁI trước.

5. Code mẫu: ba kiểu duyệt DFS​

Đang tải trình chạy code…

6. Mẫu nhận diện​

  • Dữ liệu phân cấp (thư mục, danh mục, gia phả, DOM) → cây.
  • Duyệt cây → đệ quy tự nhiên (DFS) hoặc queue (BFS theo lớp).
  • "Inorder của BST = dãy sắp xếp" là mẹo rất hay dùng.

7. 🎮 Trò chơi: Duyệt cây​

🎮 Duyệt câyCâu 1/4· Điểm 0· 🔥 0

Tiền: gốc-trái-phải. Trung: trái-gốc-phải. Hậu: trái-phải-gốc.

Duyệt TRUNG thứ tự (inorder) thăm theo thứ tự?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Cây nhị phân là cây mà mỗi nút có?
2. Ba kiểu duyệt tiền/trung/hậu thuộc nhóm nào?
3. Cây khác đồ thị tổng quát ở điểm?

9. Hoàn thành​

…

☑️ Tiếp theo: 2.5.2 — Cây tìm kiếm nhị phân (BST).