Duyệt BST để sắp xếp và giữ khóa trùng

Trên BST, duyệt giữa thăm hết các khóa nhỏ hơn ở trái, thăm gốc rồi thăm các khóa lớn hơn ở phải, nên nhận dãy tăng dần. Duyệt ngược đổi thành **phải–gốc–trái** nên nhận dãy giảm dần. Kết luận này cần điều kiện BST. Duyệt giữa một cây nhị phân bất kì chưa chắc cho dãy tăng dần. Với BST cơ bản khóa khác nhau, chèn lại 8 bị bỏ qua; vì vậy dùng nó sắp dãy [8,4,8,2] sẽ làm mất một lần xuất hiện của 8.

Để sắp xếp mà giữ đủ phần tử, dùng đúng biến thể của SGK: nhỏ hơn đi trái; lớn hơn hoặc bằng đi phải. Lúc này mọi khóa trái nhỏ hơn nút, mọi khóa phải lớn hơn hoặc bằng nút. Hàm insert_repeat khác insert đã học ở cách xử lí bằng nhau. bst_sort trả danh sách mới và giữ nguyên A. Dùng inorder và các hàm chỉ số đã có. ```python def insert_repeat(T, v): k = 0 while k < len(T) and T[k] is not None: k = left(k) if v < T[k] else right(k) if k >= len(T): T.extend([None] * (k-len(T)+1)) T[k] = v def bst_sort(A): T = Tree() for x in A: insert_repeat(T, x) result = [] inorder(T, 0, result) return result ```