Gốc ở 0, các mức ghi từ trái sang phải
Cây mẫu hoàn chỉnh được lưu bằng `T = [8,4,12,2,6,10,14]`. Chỉ số là vị trí trong mảng; nó khác với giá trị chứa tại vị trí ấy.
|Nút có chỉ số k|Công thức chỉ số|
|---|---|
|Con trái|2k+1|
|Con phải|2k+2|
|Cha, nếu k>0|(k−1)//2|
Ví dụ T[2]=12; con trái ở chỉ số 5 có giá trị 10, con phải ở chỉ số 6 có giá trị 14. Cha ở chỉ số 0 có giá trị 8. Một chỉ số con tính được chưa chắc nằm trong mảng.
Các hàm chỉ số và mức
Tree() tạo mảng rỗng. parent(0) trả None vì gốc không có cha; các hàm con và cha dùng chỉ số nguyên không âm.
```python
def Tree():
return []
def left(k):
return 2*k + 1
def right(k):
return 2*k + 2
def parent(k):
return None if k == 0 else (k-1)//2
def level(k):
if k < 0:
raise ValueError("Chỉ số phải không âm")
result = 0
while k > 0:
k = parent(k)
result += 1
return result
```
None giữ vị trí không có nút
Với cây không hoàn chỉnh, chèn None tại các vị trí trống để giữ đúng công thức chỉ số. Ví dụ `[8,4,12,None,6]` có 6 là con phải của 4. Nếu xóa ô None làm thành `[8,4,12,6]`, số 6 chuyển sang vị trí con trái của 4, thành cây khác.
None là ô không có nút thật, không phải khóa 0. Duyệt đến None thì dừng nhánh ấy. Vì vậy không thể gán None cho một nút đang có con rồi coi như đã xóa riêng nút đó: các con phía dưới sẽ không còn được đi tới qua nhánh này.
Cách biểu diễn theo chỉ số dễ quan sát nhưng có thể dùng nhiều ô trống. Với một nhánh toàn con phải, chỉ số tăng 0,2,6,14,…; vài nút thật vẫn có thể cần mảng dài. Bộ mẫu chỉ dùng dữ liệu nhỏ.
Bài luyện
Trong [8,4,12,2,6,10,14], chỉ số và giá trị con trái của nút ở chỉ số 2 là gì?
Đúng. left(2)=5 và T[5]=10.
Đã đảo giá trị với chỉ số.
1 là con trái của gốc.
6 là con phải của nút chỉ số 2.
Lời giải
Theo công thức, con trái của vị trí k=2 ở 2×2+1=5. Đọc T[5] được 10. Chỉ số 5 và khóa 10 là hai thông tin khác nhau.
Bài luyện
Vì sao không nên bỏ ô None ở vị trí 3 của [8,4,12,None,6] để tiết kiệm chỗ?
None biểu thị không có nút thật.
List cho xóa, nhưng việc ấy làm sai cách biểu diễn.
Đúng. Vị trí mang ý nghĩa cấu trúc.
Cây nhị phân không bắt buộc hoàn hảo.
Lời giải
6 ban đầu ở chỉ số 4=right(1), là con phải của 4. Bỏ ô trống làm 6 về chỉ số 3=left(1), thành con trái của 4. Giữ None giúp giữ nguyên cấu trúc cây.
Bài luyện
Theo hàm level, nút ở chỉ số 6 có mức bao nhiêu?
Chỉ số 0 mới là gốc.
Cha của chỉ số 6 ở mức 1.
Không đếm số nút trên đường đi.
Đúng. 6→2→0 có hai lần về cha.
Lời giải
parent(6)=(6−1)//2=2, parent(2)=0. Cần đi qua hai cạnh để về gốc nên level(6)=2.
Đang học