Viết hàm height T tính chiều cao của cây tìm kiếm nhị phân T

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 2 trang 45 Chuyên đề Tin học 12: : Viết hàm height(T) tính chiều cao của cây tìm kiếm nhị phân T.

Lời giải:

Để tính chiều cao của cây tìm kiếm nhị phân (BST), chúng ta có thể sử dụng phương pháp đệ quy. Chiều cao của một cây BST là độ dài của đường dẫn từ nút gốc đến nút lá xa nhất. Dưới đây là cài đặt Python cho hàm height(T) để tính chiều cao 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 height(T):

    if T is None:

        return -1  # Chiều cao của một cây rỗng là -1

    else:

        # Tính chiều cao của cây con bên trái và cây con bên phải

        left_height = height(T.left)

        right_height = height(T.right)

        # Chiều cao của cây là chiều cao lớn nhất của hai cây con cộng thêm 1

        return max(left_height, right_height) + 1

Giải thích:

- Hàm height(T) sẽ tính chiều cao của cây tìm kiếm nhị phân T bằng cách sử dụng đệ quy.

- Nếu cây T là cây rỗng (None), chiều cao của cây là -1.

- Nếu cây T không rỗng, chúng ta tính chiều cao của cây con bên trái và cây con bên phải.

- Chiều cao của cây là chiều cao lớn nhất của hai cây con cộng thêm 1 (chiều cao của nút gốc).

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:

• Khởi động trang 41 Chuyên đề Tin học 12: Quan sát cây tìm kiếm nhị phân trong hình 9.1, cùng trao đổi, thảo luận các câu hỏi sau ....

• Hoạt động 1 trang 41 Chuyên đề Tin học 12: Quan sát cách cài đặt các thuật toán duyệt trên cây tìm kiếm nhị phân và trao đổi về ý nghĩa ....

• Câu hỏi 1 trang 43 Chuyên đề Tin học 12: Cho trước dãy số A = [2,1,9,0,2,1,5]. Tạo cây tìm kiếm nhị phân T từ dãy A ....

• Câu hỏi 2 trang 43 Chuyên đề Tin học 12: Với cây T như Câu 1, nếu thực hiện thuật toán duyệt ngược thì thứ tự các khoá ....

• Hoạt động 2 trang 43 Chuyên đề Tin học 12: Trao đổi, thảo luận để giải bài toán sau: Cho trước dãy số A. Thiết kế thuật toán ....

• Câu hỏi 1 trang 45 Chuyên đề Tin học 12: Viết lại hàm BSTSort(A) thực hiện sắp xếp dãy số A theo thứ tự tăng dần ....

• Câu hỏi 2 trang 45 Chuyên đề Tin học 12: Nếu không cần cập nhật vào dãy A mà chỉ cần in ra màn hình các phần tử của A ....

• Luyện tập 1 trang 45 Chuyên đề Tin học 12: Dựa trên hàm BSTSort(A) đã biết, viết chương trình sắp xếp dãy số giảm dần theo kĩ thuật ....

• Luyện tập 2 trang 45 Chuyên đề Tin học 12: Thuật toán sắp xếp dãy sử dụng cây tìm kiếm nhị phân có độ phức tạp thời gian ....

• 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 ....

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:

• Chuyên đề Tin học 12 Bài 10: Thực hành tổng hợp với cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 11: Khái niệm đồ thị

• Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

• Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

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

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---