Chuyên đề Tin 12 CTST Bài 2.1. Cây và cây nhị phân

Quan sát sơ đồ tổ chức của một công ty ở Hình 1 ta thấy các phòng ban chức năng trong công ty được tổ chức theo hình cây. Có gốc là nút “giám đốc” và cá nút con như “Phòng tổ chức”, “Phòng kinh doanh”, “Phòng kế toán”.

a) Nút gốc, nút nhánh, nút lá ở Hình 3a:

- Nút gốc là: 2

- Nút nhánh là: 24, 11, 20, 8.

- Nút lá là: 83, 3, 10, 15, 9.

b) Mức và chiều cao của cây trong Hình 3b

Mức của cây là: 1, nút gốc ở mức 0.

Chiều cao của cây là: 3

Hình 3b là cây nhị phân. Vì mỗi nút của cây có tối đa hai cây con (cây con trái và cây con phải).

Xây dựng mảng một chiều biểu diễn cây ở Hình 7 như sau: [20, 24, 12, 2, 4, 11, 13, 38, 8, 9]. Trong đó 20 là nút gốc. Mảng được duyệt theo chiều rộng của cây, từ trên xuống dưới, từ trái sang phải.

Biểu diễn cấu trúc các tập bao lồng nhau trong Hình 8 dưới dạng cây như sau:

Cây vừa nêu có 2 mấy nút lá là: C, D, E, F.

a) Vẽ một cây nhị phân có chiều cao là 4 như sau:

b) Xây dựng mảng một chiều để biểu diễn cây này:

[A, B, C, D, E, F, G, H, I, K, N, M, L, O, P]

Vận dụng trang 31 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:

Chỉ ra các nút con của rút có giá trị là 11.

Mảng biểu diễn cây nhị phân như sau:

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