مفهوم – Tree الشجرة هي عكس الشجرة الموجودة في الطبيعة حيث أن ال Root الخاص بالشجرة يكون في أعلى الشجرة والعناصر الموجودة في البنية تسمى Nodes وتتصل ببعضها عن طريق ال Edges.

وكل Node يحتوي على بيانات أو قيمة ( Value ) ويمكن أن يكون تحته Child Node أو لا, ويطلق على العناصر في أسفل الشجرة Leaf Nodes وهي العناصر التي لا يوجد تحتها Childs ويستخدم هذا النوع من البيانات في حالة كان لديك بيانات مرتبة بشكل هرمي مثل ال Folders الموجودة في نظام التشغيل على سبيل المثال.

أو لو أردت مثال من عالم الكمبيوتر فعندنا ال HTML DOM => Document Object Model وهي الشجرة الخاصة بالعناصر، وهنا بعض التعريفات لتلخيص ما كتبناه

Root أعلى Node في الشجرة

Edge حلقة الوصل بين ال Nodes

Child عبارة عن Node يحتوي على Parent

Parent عبارة عن Node يحتوي على حلقة وصل بينه وبين Child Node

Leaf عبارة عن Node لا يوجد لديه Child Node

      tree 
      ----
       j    <-- جذر
     \   /
    f      k  
  \   /  \    /
 a     h      z    <-- أوراق

شرح أهم مصطلحات الـ Tree بمزيد من التفصيل:

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

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

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

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

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

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

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

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

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

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

العقد Node: وهو كل عنصر موجود في الشجرة، وهو المكان الذي يتم حفظ البيانات داخله.

اقرأ ايضًا:

• شرح queue في هياكل البيانات
• شرح Stack في هياكل البيانات
• شرح فكرة LinkedList في البرمجة

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

إدراج Insert – إدراج عنصر جديد في الشجرة / إنشاء شجرة.

بحث Search – البحث عن عنصر في شجرة.

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

Preorder Traversal

Inorder Traversal

Postorder Traversal

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

أنواع أشجار البيانات الثنائية Binary Tree

شجرة البيانات الثنائية الممتلئة Full

شجرة البيانات الثنائية الكاملة Complete

أشجار البيانات الثنائية التامّة Perfect

شجرة البيانات الثنائية المتوازنة Balanced

الأشجار البيانية الثنائية المتحللة degenerate (المريضة pathological)