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

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

Dưới đây là chương trình Python để tạo cây tìm kiếm nhị phân (BST) từ tập hợp số nguyên dương A:

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ã

           28

         /    \

       21      43

      /  \   /  \

    13   23 35   50

   / \    \   \    \

 10  15  22    40   52

          /     /  /

         27    30 47

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.