Câu hỏi:
01/10/2024 126
Sắp xếp mảng dùng cây tìm kiếm nhị phân
Yêu cầu: Sắp xếp một mảng số nguyên a tăng dần.
Sắp xếp mảng dùng cây tìm kiếm nhị phân
Yêu cầu: Sắp xếp một mảng số nguyên a tăng dần.
Quảng cáo
Trả lời:
Giải bởi Vietjack
Thực hiện các bước sau:
Tạo cây tìm kiếm nhị phân T tử mảng an
Duyệt giữa cây tìm kiếm nhị phân T.
Code như sau:
def insertTreeT(T, i, v):
if i len(T):
T.extend([None]*(i-len(T)+1))
if T[i]== None:
T[i] = v
elif v<T[i]:
else:
insertTreeT(T, 2*i + 1, v)
insertTreeT(T, 2*i + 2, v)
def createBSTTree (T, a):
for i in range(len(a)):
insertTreeT(T, 0, a[i])
def inOrderSort (T, i, a):
if i < len(T) and T[i] != None: inOrderSort (T, 2*i + 1, a) a.append(T[i])
inOrderSort (T, 2*i + 2, a)
def SortBST(a):
T = []
createBSTTree (T, a)
a.clear()
inOrderSort (T, 0, a)
print("Nhập mảng cần sắp xếp tăng dần: ") a = list(map(int, input().split())) SortBST(a)
print("Mảng có thứ tự tăng dần:", a)
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
Sách thầy cô Vietjack biên soạn:
- 250+ Công thức giải nhanh môn Toán 12 (chương trình mới) ( 18.000₫ )
- Sổ tay Ngữ Văn 12 (chương trình mới) ( 18.000₫ )
- Sổ tay lớp 12 các môn Toán, Lí, Hóa, Văn, Sử, Địa, KTPL (chương trình mới) ( 36.000₫ )
- Bộ đề thi tốt nghiệp 2025 các môn Toán, Lí, Hóa, Văn, Anh, Sinh, Sử, Địa, KTPL (có đáp án chi tiết) ( 36.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Để xuất giá trị các nút của cây tìm kiếm nhị phân trong Hình 1 theo thứ tự tăng dần, bạn có thể sử dụng thuật toán duyệt giữa (in-order traversal). Thuật toán này sẽ duyệt qua các nút theo trình tự: nút con bên trái, nút gốc, và nút con bên phải. Dưới đây là các bước cụ thể:
Bắt đầu từ nút gốc (38), di chuyển xuống nút con bên trái (17).
Từ nút 17, tiếp tục di chuyển xuống nút con bên trái nhất (15), đây là nút không có con bên trái nên in giá trị 15.
Quay trở lại nút 17 và in giá trị 17.
Di chuyển đến nút con bên phải của nút 17 (24) và in giá trị 24.
Quay trở lại nút gốc 38 và in giá trị 38.
Di chuyển đến nút con bên phải của nút gốc (49), rồi di chuyển xuống nút con bên trái của nó (42) và in giá trị 42.
Cuối cùng, in giá trị của nút 49.
Kết quả của thuật toán duyệt giữa sẽ là dãy số theo thứ tự tăng dần: 15, 17, 24, 38, 42, 49. Đây là cách mà các giá trị nút được xuất ra một cách có trật tự từ cây tìm kiếm nhị phân.
Lời giải
Chương trình để giúp bác thợ mộc tìm thanh gỗ đúng với kích thước đã cho.
Code như sau:
def find_wood_plank(wood_lengths, k):
Hàm này tìm kiếm thanh gỗ có kích thước k trong danh sách wood_lengths.
Parameters:
wood_lengths (list): Danh sách kích thước các thanh gỗ.
k (int): Kích thước của thanh gỗ cần tìm.
Returns:
bool: True nếu tìm thấy thanh gỗ có kích thước k, False nếu không tìm thấy.
for length in wood_lengths:
if length == k:
return True
return False
# Nhập vào danh sách các kích thước thanh gỗ và kích thước cần tìm
n = int(input("Nhập số lượng thanh gỗ: "))
wood_lengths = []
print("Nhập kích thước của từng thanh gỗ:")
for _ in range(n):
wood_lengths.append(int(input()))
k = int(input("Nhập kích thước thanh gỗ cần tìm: "))
# Kiểm tra xem có thanh gỗ có kích thước k hay không
if find_wood_plank(wood_lengths, k):
print(f"Tìm thấy thanh gỗ có kích thước {k} cm.")
else:
print(f"Không tìm thấy thanh gỗ có kích thước {k} cm.")
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
🔥 Đề thi HOT:
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Giới thiệu trí tuệ nhân tạo có đáp án
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Mô hình và các giao thức mạng có đáp án
-
Bộ 3 đề thi cuối kì 2 Tin 12 Chân trời sáng tạo có đáp án - Đề 2
-
Bộ 3 đề thi cuối kì 2 Tin 12 Cánh diều có đáp án - Đề 2
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức có đáp án
-
15 câu Trắc nghiệm Tin học 12 Chân trời sáng tạo Bài A1 có đáp án
-
Trắc nghiệm tổng hợp Tin học năm 2023 có đáp án (Phần 1)
-
Trắc nghiệm Tin học 12 Bài 1 (có đáp án): Một số khái niệm cơ bản
Nhắn tin Zalo