Em hãy đưa ra danh sách giá trị khóa các nút ở cây nhị phân (Hình 1)
Em hãy đưa ra danh sách giá trị khóa các nút ở cây nhị phân (Hình 1) trong phép duyệt cây theo thứ tự giữa và nhận xét đặc điểm của cây nhị phân cùng danh sách được đưa ra này.
Giải Chuyên đề Tin 12 Bài 3: Cây tìm kiếm nhị phân - Cánh diều
Khởi động trang 43 Chuyên đề Tin học 12: Em hãy đưa ra danh sách giá trị khóa các nút ở cây nhị phân (Hình 1) trong phép duyệt cây theo thứ tự giữa và nhận xét đặc điểm của cây nhị phân cùng danh sách được đưa ra này.
Lời giải:
Danh sách giá trị khóa các nút ở cây nhị phân (Hình 1) trong phép duyệt cây theo thứ tự giữa như sau:
1. Bắt đầu từ gốc (2), duyệt cây con trái của 2.
2. Cây con trái của 2 là 1, không có cây con trái và cây con phải. Thăm nút 1.
3. Trở lại nút gốc 2, thăm nút 2.
4. Duyệt cây con phải của 2 là 5.
5. Từ 5, duyệt cây con trái của 5 là 3.
6. Cây con trái của 3 là null, thăm nút 3.
7. Duyệt cây con phải của 3 là 4.
8. Cây con trái và cây con phải của 4 đều là null. Thăm nút 4.
9. Trở lại nút 5, thăm nút 5.
10. Duyệt cây con phải của 5 là 6, không có cây con trái và cây con phải. Thăm nút 6.
Danh sách giá trị khóa các nút theo thứ tự giữa là: 1, 2, 3, 4, 5, 6
Nhận xét đặc điểm của cây nhị phân cùng danh sách được đưa ra:
- Điều này phù hợp với đặc điểm của cây tìm kiếm nhị phân (BST). Trong cây tìm kiếm nhị phân, khi duyệt theo thứ tự giữa, các giá trị khóa luôn được liệt kê theo thứ tự tăng dần.
- Danh sách giá trị khóa được duyệt theo thứ tự giữa (In-order Traversal) của cây nhị phân này là một dãy các giá trị tăng dần.
- Như vậy, cây nhị phân này cũng là một cây tìm kiếm nhị phân.
Lời giải bài tập Chuyên đề Tin 12 Bài 3: Cây tìm kiếm nhị phân hay, chi tiết khác: