الأشجار

الشجرة هي بنية مكوّنة من عُقد (نقاط) متصلة بواسطة أحرف (خطوط).

مثال لشجرة

ما الذي يجعلها شجرة

يكون الرسم البياني شجرة إذا حقق الشرطين معاً:

1. متصل: تستطيع الوصول إلى كل عقدة من أي عقدة أخرى عبر الأحرف.
2. بلا دورات: لا يمكنك البدء من عقدة، وتتبع أحرفاً، ثم العودة لنفس العقدة دون تكرار أحرف.

قاعدة مكافئة ومفيدة جداً:

• بين أي عقدتين، يوجد بالضبط مسار بسيط واحد.

خاصية “المسار الوحيد” هي السبب الرئيسي لظهور الأشجار كثيراً في حل المسائل.

حقائق مهمة

عدد الأحرف

إذا كانت الشجرة تحتوي على n عقداً، فإنها تحتوي بالضبط على:

• n - 1 حرفاً

إضافة/إزالة أحرف

إضافة حرف واحد → تُنشئ دورة

في الشجرة، يوجد بالضبط مسار واحد بين أي عقدتين u و v.

إذا أضفت حرفاً جديداً (u, v):

• المسار القديم من u إلى v ما زال موجوداً
• بالإضافة إلى الحرف المباشر الجديد

إذن أصبح لديك حلقة: (المسار القديم u→v) + (الحرف الجديد v→u) → وهذه دورة. وتكون دورة واحدة بالضبط لأن مسار u↔︎v في الشجرة فريد.

إزالة حرف واحد → تصبح غير متصلة

كل حرف في الشجرة هو جسر. إذا أزلت حرفاً (u, v):

• لا يوجد أي طريق آخر بين u و v (وإلا لكانت هناك دورة)
• لذلك تنقسم الشجرة إلى مكوّنين منفصلين (جزئين).

تجذير الشجرة

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

بعد اختيار الجذر:

• كل عقدة (ما عدا الجذر) لها أب واحد فقط (الجار الأقرب للجذر).
• قد يكون للعقدة عدة أبناء (جيران أبعد عن الجذر).
• depth[v] = عدد الأحرف من الجذر إلى v.
• subtree(v) = v وكل ما تحتها (نسلها).

تجذير الشجرة لا يغيّر الشجرة نفسها، لكنه يعطيها اتجاهاً و“هيكل عائلي” يساعدنا في التفكير والحساب.

تمثيل الشجرة في الكود

سنفترض:

int n;                          // nodes are 0..n-1
vector<int> g[n];       // adjacency list

كل g[v] تحتوي جميع جيران العقدة v.

بناء الأب والعمق باستخدام DFS

vector<int> parent(n, -1), depth(n, 0);

void dfs(int v, int p) {
    parent[v] = p;
    for (int to : g[v]) {
        if (to == p) continue;
        depth[to] = depth[v] + 1;
        dfs(to, v);
    }
}

ماذا يعطيك هذا

• parent[v]: العقدة التي فوق v في الشجرة المُجذّرة
• depth[v]: المسافة من الجذر

حجم الشجرة الفرعية

sub[v] = عدد العقد في الشجرة الفرعية لـ v (بما فيها v).

vector<int> sub(n, 1);

void dfs_subtree(int v, int p) {
    sub[v] = 1;
    for (int to : g[v]) {
        if (to == p) continue;
        dfs_subtree(to, v);
        sub[v] += sub[to];
    }
}

استخدامات شائعة:

• حساب حجم فرع معيّن
• حساب كم زوج أو مسار “يمر” عبر حرف

ملخص سريع

• الشجرة = متصلة، ولا تحتوي دورات
• يوجد مسار وحيد بين أي عقدتين
• n عقد ⇒ n-1 حرف
• اختر جذراً لتعريف الأب/الأبناء/العمق/الشجرة الفرعية
• DFS تبني parent و depth وأحجام الأشجار الفرعية

```