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

Trang trước Trang sau

Giải Chuyên đề Tin 12 Bài 7: Cây tìm kiếm nhị phân - Kết nối tri thức

Vận dụng 2 trang 36 Chuyên đề Tin học 12: 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.

Quảng cáo

Lời giải:

Để 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 k iếm nhị phân T sử dụng kỹ thuật đệ quy.

Quảng cáo

Lời giải bài tập Chuyên đề Tin 12 Bài 7: Cây tìm kiếm nhị phân hay, ngắn gọn khác:

Quảng cáo
Quảng cáo

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

Xem thêm các tài liệu học tốt lớp 12 hay khác:

Các sản phẩm khác của Vietjack:

TÀI LIỆU CLC DÀNH CHO GIÁO VIÊN VÀ PHỤ HUYNH LỚP 12

Bộ giáo án, bài giảng powerpoint, đề thi file word có đáp án 2026 tại https://tailieugiaovien.com.vn/

Hỗ trợ zalo: VietJack Official

Tổng đài hỗ trợ đăng ký: 084 283 45 85

500+ đề thi thử tốt nghiệp THPT Quốc gia form 2026 41 tài liệu 100+ đề thi HSA,TSA,V-ACT,BCA,BQP...2026 95 tài liệu Đề thi giữa kì, cuối kì 12 254 tài liệu Chuyên đề dạy thêm Toán, Lí, Hóa... 12 71 tài liệu Đề thi HSG 12 8 tài liệu Bài giảng Powerpoint 12 42 tài liệu
Xem tất cả tài liệu

Công cụ giáo viên (2048.VN)

Tạo- trộn đề thi miễn phí từ file PDF, Word, Giao bài nhanh chóng, Hoàn toàn Free

Tạo đề, số hóa đề thi từ PDF/Word/Excel Nhập đề nhanh, trích xuất nội dung tự động. Trộn đề thành nhiều mã, Download/In đề thi offline Tạo nhiều mã đề khác nhau, xuất file hoặc in dễ dàng. Quản lý lớp học Theo dõi học sinh, điểm số và kết quả học tập trực quan. Giao bài tập, tổ chức thi kiểm tra trực tuyến Giao bài, chấm điểm và thống kê kết quả ngay trên hệ thống.
Khám phá công cụ
Trang trước Trang sau
Giải bài tập lớp 12 sách mới các môn học