Viết hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kĩ thuật đệ quy.

Để viết hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kỹ thuật đệ quy, chương trình sẽ cần một phương thức đệ quy để thực hiện việc chèn. Dưới đây là cách triển khai mẫu:

class Node:

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

def insert_recursive(root, key):

    # Nếu cây là rỗng, tạo một nút mới và trả về

    if root is None:

        return Node(key)

    # Nếu khoá nhỏ hơn khoá của nút hiện tại, chèn vào cây con bên trái

    if key < root.key:

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

    # Nếu khoá lớn hơn hoặc bằng khoá của nút hiện tại, chèn vào cây con bên phải

    else:

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

    return root

# Hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kỹ thuật đệ quy

def insert_into_binary_search_tree(T, v):

    T = insert_recursive(T, v)

    return T

# Ví dụ minh họa

if __name__ == "__main__":

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

    root = Node(5)

    root.left = Node(3)

    root.right = Node(8)

    root.left.left = Node(2)

    root.left.right = Node(4)

    root.right.left = Node(6)

    root.right.right = Node(9)

    # In cây tìm kiếm nhị phân trước khi chèn

    print("Cây tìm kiếm nhị phân trước khi chèn:")

    def inorder_traversal(node):

        if node:

            inorder_traversal(node.left)

            print(node.key, end=" ")

            inorder_traversal(node.right)

    inorder_traversal(root)

    print()

    # Chèn khoá 7 vào cây tìm kiếm nhị phân

    insert_into_binary_search_tree(root, 7)

    # In cây tìm kiếm nhị phân sau khi chèn

    print("Cây tìm kiếm nhị phân sau khi chèn:")

    inorder_traversal(root)

• Chú thích:

Node là lớp biểu diễn một nút trong cây tìm kiếm nhị phân.

insert_recursive là hàm đệ quy để chèn một khoá mới vào cây tìm kiếm nhị phân.

insert_into_binary_search_tree là hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kỹ thuật đệ quy.