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

الاشجار الثنائية 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

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

binary search tree orginal

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

bst insert

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

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

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

bst find

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

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

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

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

bst leaf remove

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

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

bst non leaf remove

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

وفى كلاس BST والذى يعتبر حاوي لكلاس Node

زيارة العقد Traversal

ولها ثلاثة انواع على حسب الترتيب

  • Preorder Traversal
  • Inorder Traversal
  • Postorder Traversal

Pre-Order Traversal

preorder

الكود بلغة بايثون

Inorder Traversal

bst inorder

الكود بلغة بايثون

Post-Order Traversal

bst post order

الكود بلغة بايثون

وفى كلاس BST

تحميل الكود كامل من جيت هب