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)

Giải Chuyên đề Tin 12 Bài 2.4: Thực hành cây tìm kiếm nhị phân - Chân trời sáng tạo

Vận dụng trang 48 Chuyên đề Tin học 12: 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.

Lời giải:

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

Code như sau:

class TreeNode:

    def __init__(self, value):

       self.value = value

       self.left = None

       self.right = None

 

def insert(root, value):

    if root is None:

        return TreeNode(value)

    else:

        if value < root.value:

           root.left = insert(root.left, value)

        else:

           root.right = insert(root.right, value)

    return root

def build_bst(values):

    root = None

    for value in values:

        root = insert(root, value)

    return root

# Tập hợp số nguyên dương A

A = {28, 21, 43, 13, 23, 35, 50, 10, 15, 22, 27, 30, 40, 47, 52}

# Tạo cây tìm kiếm nhị phân T

root = build_bst(A)

b) Vẽ minh hoạ cây T

Chúng ta sẽ lần lượt chèn các giá trị vào cây BST. Dưới đây là cách cây T sẽ trông như sau khi tất cả các giá trị đã được chèn vào:

javascript

Sao chép mã

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ưới đây là 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:

def search_bst(node, value):

    if node is None:

        return False

    if node.value == value:

        return True

    elif value < node.value:

        return search_bst(node.left, value)

    else:

        return search_bst(node.right, value)

# Kiểm tra giá trị x = 10

x = 10

if search_bst(root, x):

   print(f"Giá trị {x} có trong cây.")

else:

   print(f"Giá trị {x} không có trong cây.")

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

Dưới đây là 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:

def inorder_traversal(node, result):

    if node is not None:

       inorder_traversal(node.left, result)

       result.append(node.value)

       inorder_traversal(node.right, result)

def sorted_descending_bst(root):

    result = []

   inorder_traversal(root, result)

    return sorted(result, reverse=True)

# 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

sorted_values = sorted_descending_bst(root)

print("Các giá trị của tập hợp A được sắp xếp giảm dần:")

print(sorted_values)

Tổng hợp chương trình

Dưới đây là chương trình đầy đủ bao gồm tất cả các phần:

class TreeNode:

    def __init__(self, value):

       self.value = value

       self.left = None

       self.right = None

def insert(root, value):

    if root is None:

        return TreeNode(value)

    else:

        if value < root.value:

           root.left = insert(root.left, value)

        else:

           root.right = insert(root.right, value)

    return root

def build_bst(values):

    root = None

    for value in values:

        root = insert(root, value)

    return root

def search_bst(node, value):

    if node is None:

        return False

    if node.value == value:

        return True

    elif value < node.value:

        return search_bst(node.left, value)

    else:

        return search_bst(node.right, value)

def inorder_traversal(node, result):

    if node is not None:

       inorder_traversal(node.left, result)

       result.append(node.value)

       inorder_traversal(node.right, result)

def sorted_descending_bst(root):

    result = []

   inorder_traversal(root, result)

    return sorted(result, reverse=True)

# Tập hợp số nguyên dương A

A = {28, 21, 43, 13, 23, 35, 50, 10, 15, 22, 27, 30, 40, 47, 52}

# Tạo cây tìm kiếm nhị phân T

root = build_bst(A)

# Kiểm tra giá trị x = 10

x = 10

if search_bst(root, x):

   print(f"Giá trị {x} có trong cây.")

else:

   print(f"Giá trị {x} không có trong cây.")

 

# 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

sorted_values = sorted_descending_bst(root)

print("Các giá trị của tập hợp A được sắp xếp giảm dần:")

print(sorted_values)

Chương trình trên thực hiện các nhiệm vụ yêu cầu từ việc tạo cây tìm kiếm nhị phân, kiểm tra giá trị x = 10, đến việc sắp xếp và xuất ra màn hình các giá trị của tập hợp A theo thứ tự giảm dần.

Lời giải bài tập Chuyên đề Tin 12 Bài 2.4: Thực hành cây tìm kiếm nhị phân hay, chi tiết khác:

• Khởi động trang 46 Chuyên đề Tin học 12: Cho cây tìm kiếm nhị phân ở Hình 1 ....

• Nhiệm vụ 1 trang 46 Chuyên đề Tin học 12: Ứng dụng cây tìm kiếm nhị phân để giải bài toán tìm kiếm ....

• Nhiệm vụ 2 trang 47 Chuyên đề Tin học 12: Sắp xếp mảng dùng cây tìm kiếm nhị phân ....

• Luyện tập trang 48 Chuyên đề Tin học 12: Tìm thanh gỗ theo yêu cầu ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Chân trời sáng tạo hay, chi tiết khác:

• Chuyên đề Tin 12 Bài 3.1: Các khái niệm cơ bản của đồ thị

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

• Chuyên đề Tin 12 Bài 3.3: Duyệt đồ thị theo chiều rộng

• Chuyên đề Tin 12 Bài 3.4: Duyệt đồ thị theo chiều sâu

• Chuyên đề Tin 12 Bài 3.5: Thực hành kĩ thuật duyệt đồ thị

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)

---