Trình bày thuật toán xác định giá trị * = 34 có thuộc cây tìm kiếm nhị phân được biểu diễn ở Hình 4b hay không.

Thuật toán để xác định giá trị * = 34 có thuộc cây tìm kiếm nhị phân được biểu diễn ở Hình 4b hay không được thực hiện bằng cách duyệt cây từ gốc xuống đến khi tìm thấy giá trị hoặc đến khi không còn nút nào để duyệt. Đây là một thuật toán đệ quy hoặc lặp (iterative). Dưới đây là cả hai cách tiếp cận:

Thuật toán Đệ Quy

def search_bst_recursive(node, value):

    # Nếu node là None, nghĩa là giá trị không tồn tại trong cây

    if node is None:

        return False

    # Nếu giá trị của node hiện tại bằng với giá trị cần tìm

    if node.value == value:

        return True

    # Nếu giá trị cần tìm nhỏ hơn giá trị của node hiện tại

    elif value < node.value:

        return search_bst_recursive(node.left, value)

    # Nếu giá trị cần tìm lớn hơn giá trị của node hiện tại

    else:

        return search_bst_recursive(node.right, value)

# Giả sử root là gốc của cây và 34 là giá trị cần tìm

found = search_bst_recursive(root, 34)

if found:

   print("Giá trị 34 có trong cây")

else:

   print("Giá trị 34 không có trong cây")

Thuật toán Lặp (Iterative)

def search_bst_iterative(node, value):

    current = node

    while current is not None:

        # Nếu giá trị của node hiện tại bằng với giá trị cần tìm

        if current.value == value:

           return True

        # Nếu giá trị cần tìm nhỏ hơn giá trị của node hiện tại

        elif value < current.value:

           current = current.left

        # Nếu giá trị cần tìm lớn hơn giá trị của node hiện tại

        else:

           current = current.right

    # Nếu đã duyệt hết mà không tìm thấy

    return False

# Giả sử root là gốc của cây và 34 là giá trị cần tìm

found = search_bst_iterative(root, 34)

if found:

   print("Giá trị 34 có trong cây")

else:

   print("Giá trị 34 không có trong cây")

Mô tả chi tiết thuật toán lặp:

1. Khởi tạo:

   • Bắt đầu từ gốc của cây.

2. Duyệt cây:

   • Trong khi node hiện tại không phải là None:

     • Nếu giá trị của node hiện tại bằng giá trị cần tìm (34), trả về True.

     • Nếu giá trị cần tìm nhỏ hơn giá trị của node hiện tại, di chuyển đến con trái của node hiện tại.

     • Nếu giá trị cần tìm lớn hơn giá trị của node hiện tại, di chuyển đến con phải của node hiện tại.

3. Kết thúc:

   • Nếu đã duyệt hết cây mà không tìm thấy giá trị, trả về False.