Cho mảng các số nguyên dương A = [9, 6, 5, 17, 10, 3, 8, 12]. a) Xây dựng cây nhị phân với mảng số nguyên dương trên. b) Viết chương trình có sử dụng phép toán duyệt trước, duyệt giữa, duyệt sau để: - Kiểm tra giá trị 10 có trong cây hay không? - Kiểm

a) Xây dựng cây nhị phân với mảng số nguyên dương A = [9, 6, 5, 17, 10, 3, 8, 12]:

Chúng ta sẽ xây dựng cây nhị phân tìm kiếm (BST) từ mảng A:

1. Phần tử đầu tiên 9 là gốc.

2. 6 nhỏ hơn 9, đặt vào cây con trái của 9.

3. 5 nhỏ hơn 6, đặt vào cây con trái của 6.

4. 17 lớn hơn 9, đặt vào cây con phải của 9.

5. 10 nhỏ hơn 17, đặt vào cây con trái của 17.

6. 3 nhỏ hơn 5, đặt vào cây con trái của 5.

7. 8 lớn hơn 6, đặt vào cây con phải của 6.

8. 12 lớn hơn 10, đặt vào cây con phải của 10.

Cây nhị phân được xây dựng như sau:

b) Viết chương trình kiểm tra giá trị trong cây và thực hiện duyệt cây:

Chúng ta sẽ viết chương trình Python để thực hiện các yêu cầu.

class Node:

    def __init__(self, key):

       self.left = None

       self.right = None

        self.val = key

def insert(root, key):

    if root is None:

        return Node(key)

    else:

        if root.val < key:

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

        else:

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

    return root

def search(root, key):

    if root is None or root.val == key:

        return root

    if root.val < key:

        return search(root.right, key)

    return search(root.left, key)

def preOrder(root):

    if root:

       print(root.val, end=" ")

       preOrder(root.left)

       preOrder(root.right)

def inOrder(root):

    if root:

       inOrder(root.left)

       print(root.val, end=" ")

       inOrder(root.right)

def postOrder(root):

    if root:

       postOrder(root.left)

       postOrder(root.right)

       print(root.val, end=" ")

# Mảng số nguyên dương

A = [9, 6, 5, 17, 10, 3, 8, 12]

# Xây dựng cây nhị phân

root = None

for key in A:

    root = insert(root, key)

# Duyệt cây

print("Duyệt trước:")

preOrder(root)

print("\nDuyệt giữa:")

inOrder(root)

print("\nDuyệt sau:")

postOrder(root)

print()

# Kiểm tra giá trị

def check_value(root, value):

    if search(root, value):

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

    else:

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

# Kiểm tra giá trị 10 và 7

check_value(root, 10)

check_value(root, 7)

Giải thích chương trình:

1. Xây dựng cây nhị phân: Chúng ta sử dụng lớp Node để tạo các nút trong cây. Hàm insert được sử dụng để thêm các phần tử từ mảng vào cây.

2. Duyệt cây: Các hàm preOrder, inOrder, và postOrder được sử dụng để duyệt cây theo các phép toán duyệt trước, duyệt giữa, và duyệt sau.

3. Kiểm tra giá trị: Hàm search được sử dụng để kiểm tra xem giá trị có trong cây hay không. Hàm check_value sẽ in ra kết quả kiểm tra cho các giá trị 10 và 7.