Chèn các số vào BST, sau đó inorder traversal cho dãy đã sắp xếp.
Ví dụ
class BSTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.parent = None
def insert(self, node):
if self.key > node.key:
if self.left is None:
self.left = node
node.parent = self
else:
self.left.insert(node)
else:
if self.right is None:
self.right = node
node.parent = self
else:
self.right.insert(node)
def inorder(self):
if self.left:
self.left.inorder()
print(self.key, end=' ')
if self.right:
self.right.inorder()
class BST:
def __init__(self):
self.root = None
def add(self, key):
node = BSTNode(key)
if self.root is None:
self.root = node
else:
self.root.insert(node)
def inorder(self):
if self.root:
self.root.inorder()
tree = BST()
nums = list(map(int, input("Nhập dãy số: ").split()))
for x in nums:
tree.add(x)
print("Dãy đã sắp xếp:", end=' ')
tree.inorder()
Kết quả
Nhập dãy số: 67 54 89 0 11 34 99 Dãy đã sắp xếp: 0 11 34 54 67 89 99
Giải thích
- BSTNode: key, left, right, parent.
- Insert: nếu key nhỏ hơn -> trái, lớn hơn hoặc bằng -> phải.
- Inorder traversal của BST cho dãy tăng dần.
- Độ phức tạp trung bình O(n log n), xấu nhất O(n²) nếu cây lệch.
- Thực tế dùng
sorted()nhanh hơn.