Dựa trên tính chất của cây tìm kiếm nhị phân, hãy viết hàm minimum T và maximum T

HOT Ra mắt Sách 20 đề THPT quốc gia form 2025 toán, văn, anh.... (từ 80k/1 cuốn)

Giải Chuyên đề Tin 12 Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân - Kết nối tri thức

Vận dụng 1 trang 45 Chuyên đề Tin học 12: Dựa trên tính chất của cây tìm kiếm nhị phân, hãy viết hàm minimum(T) và maximum(T) tính giá trị khoá nhỏ nhất và lớn nhất của cây tìm kiếm nhị phân T.

Quảng cáo

Lời giải:

Dựa trên tính chất của cây tìm kiếm nhị phân (BST), giá trị nhỏ nhất của cây sẽ nằm ở nút lá bên trái cùng (nếu có) và giá trị lớn nhất sẽ nằm ở nút lá bên phải cùng (nếu có).

Dưới đây là cài đặt Python cho hai hàm minimum(T) và maximum(T) để tính giá trị khoá nhỏ nhất và lớn nhất của cây tìm kiếm nhị phân T.

class TreeNode:

def __init__(self, key):

self.left = None

self.right = None

self.val = key

def minimum(T):

# Duyệt qua các nút con bên trái cho đến khi không còn nút con nào nữa

while T.left is not None:

T = T.left

return T.val

def maximum(T):

# Duyệt qua các nút con bên phải cho đến khi không còn nút con nào nữa

while T.right is not None:

T = T.right

return T.val

Giải thích:

- Hàm minimum(T) sẽ duyệt qua cây từ nút gốc theo hướng sang trái cho đến khi không còn nút con nào bên trái nữa. Khi đó, nút hiện tại sẽ là nút có giá trị khoá nhỏ nhất của cây.

- Tương tự, hàm maximum(T) sẽ duyệt qua cây từ nút gốc theo hướng sang phải cho đến khi không còn nút con nào bên phải nữa. Khi đó, nút hiện tại sẽ là nút có giá trị khoá lớn nhất của cây.

Quảng cáo

Lời giải bài tập Chuyên đề Tin 12 Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân hay, ngắn gọn khác:

Quảng cáo

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

Xem thêm các tài liệu học tốt lớp 12 hay khác:

HOT 500+ Đề thi thử tốt nghiệp THPT, ĐGNL các trường ĐH fle word có đáp án (2025).

Sách VietJack thi THPT quốc gia 2025 cho 2k7:

TÀI LIỆU FILE WORD DÀNH CHO GIÁO VIÊN VÀ PHỤ HUYNH LỚP 12

+ Bộ giáo án, đề thi tốt nghiệp THPT, DGNL các trường các trường có lời giải chi tiết 2025 tại https://tailieugiaovien.com.vn/

+ Hỗ trợ zalo: VietJack Official

+ Tổng đài hỗ trợ đăng ký : 084 283 45 85

500+ đề thi thử tốt nghiệp THPT Quốc gia form 2025

( 128 tài liệu )

100+ đề thi ĐGNL ĐHQG Hà Nội, Tp.Hồ Chí Minh...

( 84 tài liệu )

Đề thi giữa kì, cuối kì 12

( 143 tài liệu )

Bài giảng Powerpoint Văn, Sử, Địa 12....

( 31 tài liệu )

Chuyên đề dạy thêm Toán, Lí, Hóa ...12

( 104 tài liệu )

Đề thi HSG 12

( 4 tài liệu )

xem tất cả

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.