This post is also available in: English (الإنجليزية) हिन्दी (الهندية)
في هذا المقال “شرح 6 أنواع خاصة من الأشجار الثنائية للأطفال” ، نوجهك عبر أنواع مختلفة من الأشجار الثنائية في بنية البيانات. تعرف على هذه الأنواع المختلفة من الأشجار الثنائية وأجب عن الأسئلة في اختبار في نهاية المقالة. دعونا نفهم أولاً ما هي الشجرة في بنية البيانات؟
ما هي الشجرة في بنية البيانات؟
هناك العديد من هياكل البيانات الأخرى مثل المصفوفات والقوائم المرتبطة والمكدس وقائمة الانتظار. كل هياكل البيانات هذه هي هياكل بيانات خطية. بصرف النظر عن هياكل البيانات الخطية ، هناك نوع آخر. إنها بنية بيانات غير خطية.
تخزن بنية البيانات الخطية البيانات بشكل تسلسلي، بينما تخزن بنية البيانات غير الخطية البيانات بشكل غير خطي.
تعتبر بنية البيانات غير الخطية أكثر ربحية من بنية البيانات الخطية لأن معالجة بنية البيانات غير الخطية تستغرق وقتًا. هذا هو السبب في أن هياكل البيانات غير الخطية تسمح بالوصول السريع والسهل إلى البيانات.
الشجرة عبارة عن بنية بيانات هرمية غير خطية تتصل فيها العقد في الحواف.
مصطلحات الشجرة
العقدةهي كيان يحتوي على مفتاح أو قيمة ويشير إلى عقد أخرى.
الحافةعبارة عن رابط بين عقدتين.
الجذرهو أعلى عقدة في الشجرة.
تسمى العقد الأخيرة من كل مسار العقد الطرفيةأو العقد الخارجية.
العقد التي ليست عقد طرفية تسمى العقد الداخلية.
ارتفاع العقدة هو عدد الحواف من العقدة إلى أعمق ورقة (أي أطول مسار من العقدة إلى عقدة ورقية).
عمق العقدة هو عدد الحواف من الجذر إلى العقدة.
ارتفاع الشجرة هو ارتفاع عقدة الجذر أو عمق أعمق عقدة.
درجةالعقدة هي العدد الإجمالي لفروع تلك العقدة.
إذا كان A و B عبارة عن عقدتين ، بحيث يكون ارتفاع العقدة B هو n وأن يكون ارتفاع العقدة A (n – 1) ، فإن A تسمى العقدة الأصلية B ، وتسمى B العقدة الفرعية لـ A.
تسمى عقدتان بالأشقاءإذا كان عمقهما واحدًا.
تسمى جميع العقد التي يكون أعماقها أكبر من عمق أي عقدة X العقد المنحدرة من العقدةX ، وبالمثل ، تسمى جميع العقد التي يكون أعماقها أقل من عمق أي عقدة X معينة العقد السلفية للعقدة X.
ما هي الشجرة الثنائية؟
الشجرة الثنائية هي بنية بيانات شجرة حيث يمكن أن تحتوي كل عقدة رئيسية على عقدتين فرعيتين بحد أقصى (0 أو 1 أو 2).
أنواع الأشجار الثنائية
فيما يلي أنواع مختلفة من الأشجار الثنائية:
- الشجرة الثنائية الكاملة: الشجرة الثنائية الكاملة هي نوع خاص من الشجرة الثنائية حيث تحتوي كل عقدة على اثنين أو لا يوجد أطفال. يمكننا أيضًا أن نقول أن الشجرة الثنائية الكاملة هي شجرة ثنائية يكون فيها لجميع العقد باستثناء عقد الأوراق طفلان. (العقد الورقية هي العقد الخارجية وبالتالي ليس لها عقدة فرعية)
2.شجرة ثنائية كاملة: الشجرة الثنائية هي شجرة ثنائية كاملة إذا كانت جميع المستويات مملوءة بالكامل باستثناء المستوى الأخير المحتمل والمستوى الأخير به جميع المفاتيح المتبقية قدر الإمكان.
3.شجرة ثنائية مثالية: تسمى الشجرة الثنائية بالشجرة الثنائية المثالية وفيها يكون لكل العقد الداخلية طفلان وتكون جميع العقد الورقية في نفس المستوى.
4. شجرة ثنائية متوازنة: تسمى الشجرة الثنائية المتوازنة شجرة ثنائية يكون فيها الفرق بين الشجرة الفرعية اليمنى واليسرى لكل عقدة إما 0 أو 1.
5. شجرة ثنائية منحطة (أو مرضية): شجرة ثنائية حيث تحتوي كل عقدة داخلية على عقدة فرعية واحدة فقط. هذا النوع من الشجرة الثنائية هو نفس أداء القائمة المرتبطة.
6. شجرة ثنائية منحرفة: شجرة ثنائية حيث تحتوي كل عقدة داخلية على عقدة فرعية واحدة فقط. إذا كانت جميع العقد الداخلية تحتوي على عقدة فرعية يسرى ، فإنها تسمى Left Skewed Binary Tree وإذا كانت جميع العقد الداخلية تحتوي على عقدة فرعية اليمنى ، فإنها تسمى Right Skewed Binary Tree.
تنفيذ برنامج Binary Tree في لغة ++C.
تحتوي الشجرة الثنائية على المكونات التالية:
- شجرة فرعية على اليسار
- عقدة جذر
- شجرة فرعية على اليسار
يتم استخدام الكود التالي لإنشاء شجرة ثنائية في لغة ++C:
struct node
{
int key_value;
node *left;
node *right;
};
يحتوي الجذر على key_value ويشير إلى عقدتين أخريين – واحدة إلى اليسار والأخرى إلى اليمين.
استخدام الأشجار الثنائية
على عكس المصفوفة والقائمة المرتبطة ، وهي هياكل بيانات خطية ، فإن الشجرة هي بنية بيانات هرمية (أو غير خطية).
- قد يكون أحد أسباب استخدام الأشجار هو أنك تريد تخزين المعلومات التي تشكل تسلسلاً هرميًا بشكل طبيعي. على سبيل المثال ، تنفيذ نظام ملفات على جهاز كمبيوتر.
- إذا قمنا بتنظيم المفاتيح في شكل شجرة (مع بعض الطلبات على سبيل المثال ، شجرة البحث الثنائية) ، فيمكننا البحث عن مفتاح معين بشكل أسرع مقارنة بهياكل البيانات الخطية.
