Câu hỏi:
01/10/2024 23Cho cây tìm kiếm nhị phân ở Hình 1.
Ở bài học trước, em đã được giới thiệu về việc giá trị các nút trong cây tìm kiếm nhị phân được sắp xếp theo một trình tự nhất định. Em hãy mô phỏng thuật toán để xuất giá trị các nút của cây tìm kiếm nhị phân trong Hình 1 theo thứ tự tăng dần.
Sách mới 2k7: 30 đề đánh giá năng lực DHQG Hà Nội, Tp. Hồ Chí Minh, BKHN 2025 mới nhất (600 trang - chỉ từ 160k).
Quảng cáo
Trả lời:
Để xuất giá trị các nút của cây tìm kiếm nhị phân trong Hình 1 theo thứ tự tăng dần, bạn có thể sử dụng thuật toán duyệt giữa (in-order traversal). Thuật toán này sẽ duyệt qua các nút theo trình tự: nút con bên trái, nút gốc, và nút con bên phải. Dưới đây là các bước cụ thể:
Bắt đầu từ nút gốc (38), di chuyển xuống nút con bên trái (17).
Từ nút 17, tiếp tục di chuyển xuống nút con bên trái nhất (15), đây là nút không có con bên trái nên in giá trị 15.
Quay trở lại nút 17 và in giá trị 17.
Di chuyển đến nút con bên phải của nút 17 (24) và in giá trị 24.
Quay trở lại nút gốc 38 và in giá trị 38.
Di chuyển đến nút con bên phải của nút gốc (49), rồi di chuyển xuống nút con bên trái của nó (42) và in giá trị 42.
Cuối cùng, in giá trị của nút 49.
Kết quả của thuật toán duyệt giữa sẽ là dãy số theo thứ tự tăng dần: 15, 17, 24, 38, 42, 49. Đây là cách mà các giá trị nút được xuất ra một cách có trật tự từ cây tìm kiếm nhị phân.
Đã bán 152
Đã bán 114
Đã bán 132
Đã bán 47
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Ứng dụng cây tìm kiếm nhị phân để giải bài toán tìm kiếm
Yêu cầu: Cho cây tìm kiếm nhị phần (Hình 2) biểu diễn tập hợp số nguyên dương
A = {46, 49, 31, 45, 41, 50, 47, 28, 30, 48}.
Em hãy viết chương trình kiểm tra giá trị x = 41 có xuất hiện trong tập hợp A hay không.
Câu 2:
Cho tập hợp số nguyên dương A = {28, 21, 43, 13, 23, 35, 50, 10, 15, 22, 27, 30, 40, 47, 52).
a) Viết chương trình tạo cây tìm kiếm nhị phân T biểu diễn tập hợp A.
b) Vẽ minh hoạ cây T.
c) Viết chương trình kiểm tra giá trị x = 10 có xuất hiện trong cây tìm kiếm nhị phân T hay không.
d) Viết chương trình xuất ra màn hình các giá trị của tập hợp A được sắp xếp giảm dần.
Câu 3:
Tìm thanh gỗ theo yêu cầu
Tại xưởng gỗ, bác thợ mộc cần tìm một thanh gỗ có kích thước là k (cm) trong n thanh gỗ có các kích thước khác nhau để đóng tủ.
Yêu cầu: Để giúp bác thợ mộc tìm thanh gỗ đúng với kích thước đã cho. Hãy viết chương trình.
Câu 4:
Sắp xếp mảng dùng cây tìm kiếm nhị phân
Yêu cầu: Sắp xếp một mảng số nguyên a tăng dần.
Gọi 084 283 45 85
Hỗ trợ đăng ký khóa học tại Vietjack
về câu hỏi!