โปรแกรม Python เรียงลำดับด้วย Binary Search Tree (BST)

ใช้ Binary Search Tree เรียงลำดับตัวเลข: แทรกทุกตัวเลขเข้า BST แล้วทำ Inorder Traversal จะได้ลำดับน้อยไปมาก

ตัวอย่างโค้ด

class BSTNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
    
    def insert(self, node):
        if node.key < self.key:
            if self.left is None:
                self.left = node
            else:
                self.left.insert(node)
        else:
            if self.right is None:
                self.right = node
            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()
for x in [67, 54, 89, 0, 11, 34, 99]:
    tree.add(x)

print("Sorted:")
tree.inorder()

ผลลัพธ์

Sorted: 0 11 34 54 67 89 99

คำอธิบาย

• BST Property: left < root ≤ right

• insert วางโหนดใหม่ตามกฎ BST

• Inorder Traversal ของ BST ให้ลำดับเรียงจากน้อยไปมาก

• Time: Average O(n log n), Worst O(n²) (ถ้า tree สูง)

• ไม่ควรใช้แทน sorted() ในทางปฏิบัติ แต่ดีสำหรับเรียนรู้โครงสร้างข้อมูล