الأشجار والرسوم البيانية

الأشجار والرسوم البيانية من أكثر هياكل البيانات اختبارًا في المقابلات. تختبر قدرتك على التفكير التكراري واجتياز الهياكل المعقدة.

الأشجار الثنائية (Binary Trees)

الشجرة الثنائية هي شجرة حيث كل عقدة لها طفلان كحد أقصى. الاجتيازات الثلاث الأساسية:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Inorder: يسار -> جذر -> يمين (يعطي ترتيبًا مرتبًا في BST)
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Preorder: جذر -> يسار -> يمين (يُستخدم للتسلسل)
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# Postorder: يسار -> يمين -> جذر (يُستخدم للحذف)
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

مسائل الأشجار الرئيسية في المقابلات:

المسألة	النهج	التعقيد
أقصى عمق	DFS تكراري	O(n)
فحص تطابق شجرتين	DFS للمقارنة	O(n)
عكس شجرة ثنائية	DFS مع تبديل الأطفال	O(n)
أدنى سلف مشترك	DFS	O(n)
التحقق من BST	اجتياز Inorder	O(n)
اجتياز مستوى بمستوى	BFS مع طابور	O(n)

# أقصى عمق للشجرة الثنائية
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# التحقق من BST
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    if root.val <= min_val or root.val >= max_val:
        return False
    return (is_valid_bst(root.left, min_val, root.val) and
            is_valid_bst(root.right, root.val, max_val))

الرسوم البيانية (Graphs)

الرسوم البيانية هي شبكات من العُقد (الرؤوس) المتصلة بأضلاع. يمكن أن تكون:

• موجّهة أو غير موجّهة
• موزونة أو غير موزونة
• دورية أو لا دورية

التمثيل:

# قائمة التجاور (الأكثر شيوعًا في المقابلات)
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D', 'E'],
    'D': [],
    'E': []
}

# قائمة الأضلاع
edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D'), ('C', 'E')]

DFS و BFS للرسوم البيانية:

# DFS (تكراري)
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# BFS (تكراري مع طابور)
from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

الترتيب الطوبولوجي (Topological Sort)

يُستخدم لحل التبعيات (جدولة المقررات، أنظمة البناء):

def topological_sort(graph):
    # حساب درجات الدخول
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    # البدء بالعُقد التي ليس لها تبعيات
    queue = deque([n for n in in_degree if in_degree[n] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # إذا لم تتضمن النتيجة كل العُقد، هناك دورة
    return result if len(result) == len(graph) else []

نصيحة للمقابلات: عندما ترى "تبعيات" أو "متطلبات مسبقة" أو "ترتيب" في مسألة، فكّر في الترتيب الطوبولوجي.

---

التالي: سنغطي الأكوام وهياكل البيانات المتقدمة التي تظهر في مسائل Top-K والمسائل القائمة على الأولوية. :::