هياكل بيانات : Binary Tree الاشجار الثنائية

الاشجار الثنائية Binary Tree طريقة من طرق تمثيل البيانات فى الذاكرة.

الاشجار الثنائية تحتوي على عقدتين او اكثر.

كل عقدة تحتوي على ثلاثة اشياء :

البيانات
مؤشر يشير لعنوان الابن الايمن
مؤشر يشير لعنوان الابن الايسر

قبل الشروع فى شرح Binary tree يجب معرفة بعض المصطلحات المستخدمة فيها

المسار Path – ويعنى تسلسل العقد Nodes.

الجذر Root – العقدة في الجزء العلوي من الشجرة تسمى الجذر. هناك جذر واحد فقط لكل شجرة ومسار واحد وفريد من عقدة الجذر إلى أي عقدة اخرى.

الاب Parent – أي عقدة باستثناء عقدة الجذر لها ابن واحد على الاقل تسمى الاب.

ابن Child – وهىالعقدة الموجودة أسفل عقدة الاب والمتصلة بها من الأسفل.

Leaf – تسمى العقدة التي لا تحتوي على أي عقدة تابعة (ابناء) باسم leaf.

الشجرة الفرعية Subtree – شجرة فرعية من الشجرة الاساسية.

الزيارة Visiting – وتعنى التحقق من قيمة العقدة عند المرور بها.

Traversing – المرور عبر العقد بترتيب معين.

Levels المستويات – وتعنى مستو العقدة ويكون الجذر فى المستو 0 ويتبعه الابناء فى المستويات 1 و 2 والخ.

المفاتيح keys – يمثل المفتاح قيمة العقدة.

العمليات الاساسية فى Binary Search Tree

إدراج Insert – إدراج عنصر جديد في الشجرة / إنشاء شجرة.
بحث Search – البحث عن عنصر في شجرة.
حذف Remove – حذف عنصر معين من الشجرة.
Preorder Traversal
Inorder Traversal
Postorder Traversal

لاحظ Preorder Traversal , Inorder Traversal , Postorder Traversal هى طرق لزيارة كل عقد الشجرة -للحصول على

قيمها مثلًا

ادراج عنصر فى الشجرة Insert

لناخذ مثال على الشجرة التالية

نفترض الآن اننا نريد ادراج القيمة 63 فى الشجرة.

الكود للجزء السابق بلغة بايثون كالتالى

ايجاد عنصر معين فى الشجرة

نفترض الآن اننا نريد ايجاد القيمة 42 فى الشجرة.

الكود لهذا الجزء بلغة بايثون

حذف عنصر معين من الشجرة

فى حالة كانت العقدة Leaf

يتم ايجاد العنصر كما فعلنا سابقًا ثم نجعل قيمه ب None.

فى حالة لم تكن العقدة Leaf.

يتم ايجاد العقدة المراد حذفها اولًا وهو 75 فى المثال هذا, بعد ذلك نقوم بتحريك الشجرة الفرعية إلى اعلى عن طريق وضع القيمة 60 فى مكان القيمة 75 ثم جعل العقدة 60 ب None.