شجرة (بنية بيانات)
المحتويات
- شجرة النحو المجرد للغات الحاسب
- التطبيقات
- طرق الفحص والبحث
- المصطلحات
- شجرة الحوار لتوليد المحادثات
- المسارات
- البحث عن عقدة
- السعة: عدد الأوراق
- الجار: عقدة الأصل أو الفرع منها
- درجة العقدة: تحدد بعدد العقد الفرعية لها
- التمثيل في الذاكرة
- الصور المولدة بالحاسب
- هيكل الدليل المستخدم لتنظيم الدلائل الفرعية والملفات
- التجميع الهرمي
- هياكل بيانات

على سبيل التعريف، الشجرة في سياق علوم الحاسب هي أحد أشهر أنواع هياكل البيانات، تأخذ شكل هرمي مكون من عُقد تتصل جميعا ببعضها البعض، وتُعتبر العُقدة أصلية بالنسبة لما اتصل بها من أسفل وتُعتبر فرعية بالنسبة لما اتصل بها من أعلى (انظر الشكل المقابل)، وترتبط كل عقدة أصلية بعقدة فرعية واحدة أو أكثر حسب نوع الشجرة، وجميع العُقد الفرعية متصلة بعُقد أصلية باستثناء عقدة الجذر، التي تمثل رأس الشجرة أو العقدة العليا في التسلسل الهرمي للشجرة. وهذا التصميم يضمن عدم وجود حلقات أو دوائر في الشجرة، وبذلك يُمكن لتقنية العودية أن تمسح (تفحص) هيكلة الشجرة. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
وفي هذا الصدد، تُسمى الشجرة التي يتفرع فيها من كل عقدة أصلية عقدتين فرعيتين بحد أقصى باسم الشجرة الثنائية، وهي أكثر الأنواع استخداما، وبترتيب درجة العُقد الفرعية تُصبح الشجرة مرتبة من منظور نظرية الرسم البياني.
شجرة النحو المجرد للغات الحاسب
- معالجة اللغة الطبيعية في:
- شجرة التحليل
- نمذجة الكلام في النحو التوليدي
التطبيقات
كذلك، يُستعمل هيكل الشجرة لتمثيل البيانات الهرمية الشكل ومعالجتها في عدد من التطبيقات مثل:
نظام الملفات في:
طرق الفحص والبحث
وفي السياق ذاته، الفحص السابق الترتيب: العقدة الأصلية ⬅ العقدة الفرعية اليسرى ⬅ العقدة الفرعية اليمينى.
وعلى صعيد آخر، كما يمكن البحث عن عقدة معينة في الشجرة باستخدام خوارزمية بحث الاتساع أولا، حيث تبدأ الخوارزمية البحث من عقدة الجذر ثم عقد المستوى التالى حتى إنهائه ثم الانتقال للمستوى الذي يليه، حتى انتهاء بحث جميع المستويات وجميع عقد الشجرة. أو باستخدام خوارزمية بحث العمق أولا، التي تبدأ البحث من عقدة الجذر إلى أقصى عمق أولا ثم إلى العمق الذي يليه، حتى انتهاء بحث جميع عقد الشجرة.
وفي هذا الصدد، يبدأ فحص عقد الشجرة (والذي يُعرف كذلك بالتجول في عقد الشجرة) من اليسار إلى اليمين وبطرق مختلفة، تختلف حسب ترتيب فحص العقدة الأصلية بالنسبة للعقدتين المتفرعتين منها، والطرق المعروفة هي:
وعلى صعيد آخر، الفحص الوسط الترتيب: العقدة الفرعية اليسرى ⬅ العقدة الأصلية ⬅ العقدة الفرعية اليمينى
وفي السياق ذاته، الفحص اللاحق الترتيب: العقدة الفرعية اليسرى ⬅ العقدة الفرعية اليمينى ⬅ العقدة الأصلية
المصطلحات
وفي هذا السياق، تُمثل العقدة حيز أو مكان لحفظ البيانات، وتتصل العُقدة بمثيلاتها (العقد الأخرى) بروابط تسمى أحيانًا الحواف. ويُمكن أن يتفرع من كل عقدة عند أسفلها عدد من العقد تُسمى بالعقد الفرعية (أو عقدة الابن) وتُعرف حينها عقدة الأصل بالعقدة الأصلية (أو عقدة الأب)، وتسمى العقد الفرعية من نفس الأصل بالعُقد الشقيقة، وعادةً ما تكون مرتبة من اليسار إلى اليمين، وجميع العقد متفرعة من غيرها عدا العقدة الجذرية أو عقدة الجذر. كما يمكن تقسيم العقد إلى داخلية وخارجية حسب وجود تفريع، فالعقدة التي يتفرع منها عقد أخرى تُسمى عقدة داخلية، أما العقدة التي لا يتفرع منها أي عقد فتسمى عقدة خارجية (المعروفة كذلك باسم العقدة الطرفية أو العقد الورقية). ويُمثَل ارتفاع أي عقدة بطول أقصى مسار بينها وبين العقدة الطرفية، فيما يُمثَل عمق أي عقدة بطول أقصى مسار بينها وبين عقدة الجذر. وبالتالي فإن عمق عقدة الجذر يساوي صفر، وارتفاع العقد الورقية يساوي صفر.، وتشمل المصطلحات الأخرى المستعملة ما يلي:
شجرة الحوار لتوليد المحادثات
كذلك، نماذج كائنات المستند لمستندات لغة التوصيف القابلة للتوسعة ولغة توصيف النص الفائق
تمثيل خوارزميات الترتيب
إضافةً إلى ذلك، شجرة البحث التي تُخزن البيانات بطريقة تُمكن خوارزميات البحث من مسح هيكلة الشجرة بشكل فعال، وأشهرها شجرة البحث الثنائية
المسارات
- كما تُستعمل الهياكل الشجرية لرسم خرائط العلاقات بين الأشياء، مثل:
- المكونات الأصلية والفرعية في رسم العرض التفصيلي
- استدعاءات الدالة الفرعية
- وراثة الحمض النووي في الكائنات الحية
البحث عن عقدة
- إضافة عقدة جديد في موضع معين على الشجرة
- حذف عقدة
- التقليم : إزالة جزء كامل من الشجرة
- التطعيم : إضافة قسم كامل إلى شجرة
- العثور على العقدة الأصلية لأي عقدة فرعية
- العثور على الأصل المشترك لعقدتين فرعيتين
السعة: عدد الأوراق
- الشجرة المرتبة: شجرة تُرتب فيها العقد الفرعية بنظام معين.
- حجم الشجرة: عدد العقد الكلية للشجرة.
- أمثلة على هيكل الشجرة وغيرها
- العمليات الشائعة علي هيكل الشجرة
- تعداد جميع العقد أو جزء منها
الجار: عقدة الأصل أو الفرع منها
الخلف: فروع أي عقدة أصلية انتهاء إلى العقد الطرفية
السلف: أصول أي عقدة الفرعية انتهاءا لعقدة الجذر.
درجة العقدة: تحدد بعدد العقد الفرعية لها
- درجة الشجرة: أقصى عدد متاح للعقد الفرعية المحتملة لأصل واحد
- المسافة: عدد حواف أقصر مسار بين عقدتين.
- مستوى العقدة: عدد حواف أقصر مسار بينها وبين عقدة الجذر. وهو نفسه.
- العرض: عدد العقد في المستوى.
التمثيل في الذاكرة
أنظر كذلك
ومن جهة أخرى، هناك الكثير من الطرق المختلفة لتمثيل الأشجار في الذاكرة العاملة، وعادةً ما يتم تخصيص سجلات ديناميكية تشير لمكان العقد الأصلية لها أو الفرعية منها أو كليهما، وإذا كان حجمها ثابتًا فيمكن تخزينها في قائمة. وتُمثل عقد الشجرة في قواعد البيانات العلائقية على شكل صفوف جدول، مع معرفات الصفوف المفهرسة لتسهيل المؤشرات بين العقد الأصلية والفرعية. كما يمكن كذلك تخزين العقد كعناصر في مصفوفة حاسوبية، مع تحديد العلاقات بين عقدها حسب مواقعها في المصفوفة (كما في الكومة).
الصور المولدة بالحاسب
- أشجار محاكاة بارنز هت المستعملة في محاكاة المجرات
- تمثل الأكوام (إحدى أشكال هياكل البيانات)
- التصنيفات الهرمية مثل تصنيف ديوي العشري
- البرمجة الوراثية
هيكل الدليل المستخدم لتنظيم الدلائل الفرعية والملفات
وعلى صعيد آخر، التسلسل الهرمي للأصناف (أو شجرة الوراثة) الذي يوضح العلاقة بين الأصناف في البرمجة كائنية التوجه.
وفي السياق ذاته، الآلية المستعملة لتخصيص وربط كتل البيانات الموجودة على جهاز التخزين
التجميع الهرمي
التسلسل الهرمي الرياضي
من جانب آخر، كما يمكن استخدام هيكل الشجرة لتمثيل ومعالجة الهياكل الرياضية المختلفة، مثل:
هياكل بيانات
في هذا الإطار، تصنيف: أشجار (هياكل البيانات) (أنواع كتالوجات الأشجار الحسابية)
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟