khoahoc.vietjack.com
Xin chào! Vào học

Câu hỏi:

01/10/2024 354 Lưu

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 tra giá trị 7 có trong cây hay không?

Quảng cáo

Trả lời:

verified Giải bởi Vietjack

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:

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

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

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

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

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

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

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

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

Media VietJack

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

Code:

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)

 


 

Đang tải chế độ Học...

Dành cho bạn Hot

Lớp 12 Vật lý
210 người thi tuần này

Trắc nghiệm Mô hình động học phân tử chất khí lớp 12 (có đáp án)

15 câu 1.9 K lượt thi Thi ngay →
Lớp 12 Tiếng Anh
138 người thi tuần này

Đề cương ôn tập giữa kì 1 Tiếng Anh 12 Global Success có đáp án

45 câu 1.3 K lượt thi Thi ngay →
Lớp 12 Sinh học
158 người thi tuần này

10 câu trắc nghiệm Sinh học 12 Kết nối tri thức Bài 8 có đáp án

10 câu 2 K lượt thi Thi ngay →
Lớp 12 Lịch sử
2,339 người thi tuần này

20 câu trắc nghiệm Lịch sử 12 Kết nối tri thức Bài 1 có đáp án

20 câu 22.4 K lượt thi Thi ngay →
Lớp 12 Địa lý
406 người thi tuần này

20 câu Trắc nghiệm Địa lý 12 Kết nối tri thức Bài 2 có đáp án

25 câu 6 K lượt thi Thi ngay →
Lớp 12 Tin học
574 người thi tuần này

15 câu Trắc nghiệm Tin học 12 Kết nối tri thức có đáp án

15 câu 13.2 K lượt thi Thi ngay →
Lớp 12 Giáo dục Kinh tế và Pháp luật
656 người thi tuần này

15 Câu trắc nghiệm KTPL 12 Kết nối tri thức Bài 1 có đáp án

15 câu 8.9 K lượt thi Thi ngay →

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

Mảng một chiều để biểu diễn các giá trị trong cây nhị phân như sau:

[2, 24, 11, None, 3, 8, 9]

Lời giải

Cho các thao tác: (1) Duyệt nút gốc; (2) Duyệt cây con trái; (3) Duyệt cây con phải. Sắp xếp thứ tự các thao tác tương ứng với các phép toán duyệt cây nhị phân:

a) Duyệt trước:

Thao tác: Duyệt nút gốc -> Duyệt cây con trái -> Duyệt cây con phải

Thứ tự: (1) -> (2) -> (3)

b) Duyệt giữa:

Thao tác: Duyệt cây con trái -> Duyệt nút gốc -> Duyệt cây con phải

Thứ tự: (2) -> (1) -> (3)

c) Duyệt sau:

Thao tác: Duyệt cây con trái -> Duyệt cây con phải -> Duyệt nút gốc

Thứ tự: (2) -> (3) -> (1)

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Xem trọn bộ đề thi 7 câu hỏi
Xem thêm