Python Data Structures – Binary Trees

تُعد البنية الشجرية الثنائية (Binary Tree) واحدة من أكثر التراكيب البيانية شيوعًا واستخدامًا في علم الحاسوب، حيث تُستخدم لتمثيل البيانات بطريقة هرمية. تتكون الشجرة الثنائية من عقد (Nodes)، وكل عقدة تحتوي على قيمة ومؤشران يُشيران إلى العقدتين الأبناء (اليسرى واليمنى). البنية الشجرية الثنائية تُعتبر الأساس لتراكيب بيانات أخرى أكثر تعقيدًا مثل شجرة البحث الثنائية (Binary Search Tree) والشجرة المتوازنة (Balanced Tree).

الأساسيات والمفاهيم الأولية للشجرة الثنائية

لفهم كيفية عمل الشجرة الثنائية، يجب أولاً التعرف على بعض المفاهيم الأساسية. في الشجرة الثنائية، يمكن أن تحتوي كل عقدة على عقدة فرعية يسرى وعقدة فرعية يمنى. العقدة التي لا تحتوي على أي أبناء تُسمى عقدة ورقية (Leaf Node). الجذر (Root) هو العقدة الأولى أو العليا في الشجرة. الشجرة قد تكون فارغة، أي لا تحتوي على أي عقد، أو تحتوي على عقدة جذر واحدة فقط.

الشجرة الثنائية يمكن تمثيلها في بايثون باستخدام الفئات (Classes). يمكننا تعريف فئة تمثل عقدة واحدة تحتوي على قيمة ومؤشرين للأبناء. فيما يلي مثال بسيط لكيفية إنشاء شجرة ثنائية في بايثون:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if not self.root:
            self.root = Node(value)
        else:
            self._insert_recursively(self.root, value)

    def _insert_recursively(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert_recursively(node.left, value)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert_recursively(node.right, value)

التنقل في الشجرة الثنائية والأساليب الشائعة

التنقل في الشجرة الثنائية يمكن أن يتم بعدة طرق، وأشهرها الترتيب (Inorder) والسابقة (Preorder) واللاحقة (Postorder). كل طريقة من هذه الطرق لها استخداماتها الخاصة وتُستخدم لأغراض مختلفة. على سبيل المثال، الترتيب (Inorder Traversal) يزور العقد بالترتيب من الأصغر إلى الأكبر في شجرة البحث الثنائية.

يمكننا كتابة دوال في بايثون لتنفيذ كل نوع من عمليات التنقل. هنا مثال على كيفية تنفيذ الترتيب (Inorder Traversal):

def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)

# استخدام المثال
tree = BinaryTree()
tree.insert(10)
tree.insert(5)
tree.insert(15)
inorder_traversal(tree.root)

بهذا الشكل، نكون قد استعرضنا كيفية بناء الشجرة الثنائية في بايثون وكيفية التنقل عبرها باستخدام طرق مختلفة. تُعد الشجرة الثنائية أداة قوية لتنظيم البيانات بشكل يتيح الوصول السريع والفعال.