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.

Quảng cáo

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ã

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)

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.

Quảng cáo

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: