Cho mảng một chiều A biểu diễn cho một cây nhị phân hoàn chỉnh như sau
Cho mảng một chiều A biểu diễn cho một cây nhị phân hoàn chỉnh như sau:
Giải Chuyên đề Tin 12 Bài 2.1: Cây và cây nhị phân - Chân trời sáng tạo
Vận dụng trang 31 Chuyên đề Tin học 12: Cho mảng một chiều A biểu diễn cho một cây nhị phân hoàn chỉnh như sau:
|
2 |
24 |
11 |
8 |
3 |
8 |
9 |
1 |
2 |
3 |
4 |
Chỉ ra các nút con của rút có giá trị là 11.
Lời giải:
Mảng biểu diễn cây nhị phân như sau:
|
Mảng |
2 |
24 |
11 |
8 |
3 |
8 |
9 |
1 |
2 |
3 |
4 |
|
Thứ tự |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
Ta thấy nút có giá trị là 11 nằm ở vị trí thứ 3 trong mảng.
Xác định các nút con của nút tại vị trí 3
- Nút con trái của nút tại vị trí i hay còn gọi là vị trí số 3 sẽ nằm ở vị trí 2*i = 2*3=6
- Nút con phải của nút tại vị trí i hay còn gọi là vị trí số 3 sẽ nằm ở vị trí 2*i + 1=2*3+1=7
Giá trị của các nút con tại vị trí 6 có giá trị là 8. Nút tại vị trí 7 có giá trị là 9.
Vậy, các nút con của nút có giá trị 11 là: Nút con trái: 8. Nút con phải: 9
Lời giải bài tập Chuyên đề Tin 12 Bài 2.1: Cây và cây nhị phân hay, chi tiết khác: