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
Sắp xếp mảng dùng cây tìm kiếm nhị phân
Giải Chuyên đề Tin 12 Bài 2.4: Thực hành cây tìm kiếm nhị phân - Chân trời sáng tạo
Nhiệm vụ 2 trang 47 Chuyên đề Tin học 12: 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.
Lời giải:
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)
Lời giải bài tập Chuyên đề Tin 12 Bài 2.4: Thực hành cây tìm kiếm nhị phân hay, chi tiết khác: