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)
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Đang tải chế độ Học...
Hot: 1000+ đề thi giữa kì 1 lớp 1-12 đầy đủ các môn (Update 2026) (chỉ từ 60k). Tải ngay
Đăng ký VIP để học và luyện thi không giới hạn
Trọn bộ quyền lợi trên Vietjack, trong một tài khoản.
- Phòng luyện thi cấp tốc: ĐGNL - ĐGTD, Tốt nghiệp THPT, Ôn vào 10, Ôn vào 6, Ôn Giữa kì/Cuối kì
- Hơn 200K đề thi thử, đề minh hoạ, chính thức các năm
- Với 3tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
- Tải xuống đề thi [DOCX] với đầy đủ đáp án
- Xem hàng ngàn bài giảng đính kèm củng cố thêm kiến thức
- Bao gồm tất cả các bậc từ Tiểu học đến Đại học
- Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện
- Đăng ký ngay
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
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.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
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.")
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
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.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
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.
Đăng ký để học cùng Vietjack. Hoàn toàn miễn phí!
Bằng việc đăng ký, bạn đồng ý với Điều khoản sử dụng và Chính sách bảo mật của Vietjack.
Nhắn tin Zalo
Hỏi bài tập