تعني الشجرة الثنائية أن العقدة يمكن أن تحتوي على طفلين كحد أقصى. هنا، الاسم الثنائي نفسه يشير إلى أن 'اثنين'؛ لذلك، يمكن أن تحتوي كل عقدة على 0 أو 1 أو 2 من الأطفال.
دعونا نفهم الشجرة الثنائية من خلال مثال.
الشجرة المذكورة أعلاه هي شجرة ثنائية لأن كل عقدة تحتوي على أقصى طفلين. ويرد أدناه التمثيل المنطقي للشجرة أعلاه:
في الشجرة أعلاه، تحتوي العقدة 1 على مؤشرين، أي مؤشر لليسار ومؤشر لليمين يشيران إلى العقدة اليسرى واليمنى على التوالي. تحتوي العقدة 2 على كلا العقدتين (العقدة اليسرى واليمنى)؛ ولذلك، فإنه يحتوي على مؤشرين (يسار ويمين). العقد 3 و5 و6 هي العقد الورقية، لذا تحتوي كل هذه العقد باطل المؤشر على كلا الجزأين الأيسر والأيمن.
خصائص الشجرة الثنائية
- في كل مستوى من i، الحد الأقصى لعدد العقد هو 2أنا.
- يتم تعريف ارتفاع الشجرة على أنه أطول مسار من العقدة الجذرية إلى العقدة الورقية. الشجرة الموضحة أعلاه لها ارتفاع يساوي 3. وبالتالي، فإن الحد الأقصى لعدد العقد عند الارتفاع 3 يساوي (1+2+4+8) = 15. بشكل عام، الحد الأقصى لعدد العقد الممكنة عند الارتفاع h هو (20+ 21+ 22+….2ح) = 2ح+1-1.
- الحد الأدنى لعدد العقد الممكنة عند الارتفاع h يساوي ح+1 .
- إذا كان عدد العقد هو الحد الأدنى، فإن ارتفاع الشجرة سيكون الحد الأقصى. على العكس من ذلك، إذا كان عدد العقد هو الحد الأقصى، فسيكون ارتفاع الشجرة هو الحد الأدنى.
إذا كان هناك عدد 'n' من العقد في الشجرة الثنائية.
يمكن حساب الحد الأدنى للارتفاع على النحو التالي:
وكما نعلم ذلك،
ن = 2ح+1-1
ن+1 = 2ح+1
أخذ السجل على كلا الجانبين،
الأعرج تغيير اللون
سجل2(ن+1) = سجل2(2ح+1)
سجل2(ن+1) = ح+1
ح = سجل2(ن+1) - 1
يمكن حساب الحد الأقصى للارتفاع على النحو التالي:
وكما نعلم ذلك،
ن = ح+1
ح= ن-1
أنواع الشجرة الثنائية
هناك أربعة أنواع من الشجرة الثنائية:
1. شجرة ثنائية كاملة/مناسبة/صارمة
تُعرف الشجرة الثنائية الكاملة أيضًا بالشجرة الثنائية الصارمة. لا يمكن اعتبار الشجرة شجرة ثنائية كاملة إلا إذا كانت كل عقدة يجب أن تحتوي على 0 أو 2 من الأطفال. يمكن أيضًا تعريف الشجرة الثنائية الكاملة على أنها الشجرة التي يجب أن تحتوي كل عقدة فيها على طفلين باستثناء العقد الورقية.
دعونا نلقي نظرة على المثال البسيط للشجرة الثنائية الكاملة.
في الشجرة أعلاه، يمكننا ملاحظة أن كل عقدة إما تحتوي على صفر أو طفلين؛ ولذلك، فهي شجرة ثنائية كاملة.
خصائص الشجرة الثنائية الكاملة
- عدد العقد الطرفية يساوي عدد العقد الداخلية زائد 1. في المثال أعلاه، عدد العقد الداخلية هو 5؛ وبالتالي فإن عدد العقد الورقية يساوي 6.
- الحد الأقصى لعدد العقد هو نفس عدد العقد في الشجرة الثنائية، أي 2ح+1-1.
- الحد الأدنى لعدد العقد في الشجرة الثنائية الكاملة هو 2*h-1.
- الحد الأدنى لارتفاع الشجرة الثنائية الكاملة هو سجل2(ن+1) - 1.
- يمكن حساب الحد الأقصى لارتفاع الشجرة الثنائية الكاملة على النحو التالي:
ن= 2*ح - 1
ن+1 = 2*ح
ح = ن+1/2
شجرة ثنائية كاملة
الشجرة الثنائية الكاملة هي شجرة يتم فيها ملء جميع العقد بالكامل باستثناء المستوى الأخير. في المستوى الأخير، يجب أن تكون جميع العقد على اليسار قدر الإمكان. في الشجرة الثنائية الكاملة، يجب إضافة العقد من اليسار.
لنقم بإنشاء شجرة ثنائية كاملة.
عند النقر على جافا سكريبت
الشجرة أعلاه عبارة عن شجرة ثنائية كاملة لأن جميع العقد مملوءة بالكامل، وتتم إضافة جميع العقد في المستوى الأخير على اليسار أولاً.
خصائص الشجرة الثنائية الكاملة
- الحد الأقصى لعدد العقد في الشجرة الثنائية الكاملة هو 2ح+1- 1.
- الحد الأدنى لعدد العقد في الشجرة الثنائية الكاملة هو 2ح.
- الحد الأدنى لارتفاع الشجرة الثنائية الكاملة هو سجل2(ن+1) - 1.
- الحد الأقصى لارتفاع الشجرة الثنائية الكاملة هو
شجرة ثنائية مثالية
تعتبر الشجرة شجرة ثنائية مثالية إذا كانت جميع العقد الداخلية بها طفلان، وكانت جميع العقد الورقية على نفس المستوى.
دعونا نلقي نظرة على مثال بسيط لشجرة ثنائية مثالية.
الشجرة أدناه ليست شجرة ثنائية مثالية لأن جميع العقد الورقية ليست على نفس المستوى.
ملاحظة: جميع الأشجار الثنائية الكاملة هي الأشجار الثنائية الكاملة بالإضافة إلى الشجرة الثنائية الكاملة، ولكن العكس غير صحيح، أي أن جميع الأشجار الثنائية الكاملة والأشجار الثنائية الكاملة هي الأشجار الثنائية الكاملة.
شجرة ثنائية منحلة
الشجرة الثنائية المتدهورة هي شجرة تحتوي جميع العقد الداخلية فيها على فرع واحد فقط.
دعونا نفهم الشجرة الثنائية المنحلة من خلال الأمثلة.
الشجرة المذكورة أعلاه عبارة عن شجرة ثنائية متدهورة لأن جميع العقد لها طفل واحد فقط. تُعرف أيضًا باسم الشجرة المنحرفة لليمين حيث أن جميع العقد لها طفل مناسب فقط.
النوم في شبيبة
الشجرة المذكورة أعلاه هي أيضًا شجرة ثنائية متدهورة لأن جميع العقد لها طفل واحد فقط. تُعرف أيضًا باسم الشجرة المنحرفة إلى اليسار حيث أن جميع العقد لها فرع أيسر فقط.
شجرة ثنائية متوازنة
الشجرة الثنائية المتوازنة هي شجرة تختلف فيها الشجرة اليمنى واليسرى بمقدار 1 على الأكثر. على سبيل المثال، AVL و أشجار حمراء وسوداء هي شجرة ثنائية متوازنة.
دعونا نفهم الشجرة الثنائية المتوازنة من خلال الأمثلة.
الشجرة المذكورة أعلاه هي شجرة ثنائية متوازنة لأن الفرق بين الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى هو صفر.
الشجرة المذكورة أعلاه ليست شجرة ثنائية متوازنة لأن الفرق بين الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى أكبر من 1.
تنفيذ الشجرة الثنائية
يتم تنفيذ الشجرة الثنائية بمساعدة المؤشرات. يتم تمثيل العقدة الأولى في الشجرة بمؤشر الجذر. تتكون كل عقدة في الشجرة من ثلاثة أجزاء، أي البيانات والمؤشر الأيسر والمؤشر الأيمن. لإنشاء شجرة ثنائية، نحتاج أولاً إلى إنشاء العقدة. سنقوم بإنشاء العقدة المعرفة من قبل المستخدم كما هو موضح أدناه:
struct node { int data, struct node *left, *right; } في الهيكل أعلاه، بيانات هي القيمة، المؤشر الأيسر يحتوي على عنوان العقدة اليسرى، و المؤشر الصحيح يحتوي على عنوان العقدة الصحيحة.
برنامج الشجرة الثنائية في لغة C
#include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } يقوم الكود أعلاه باستدعاء وظيفة create() بشكل متكرر وإنشاء عقدة جديدة في كل استدعاء متكرر. عندما يتم إنشاء جميع العقد، فإنها تشكل بنية شجرة ثنائية. تُعرف عملية زيارة العقد باسم اجتياز الشجرة. هناك ثلاثة أنواع من عمليات الاجتياز المستخدمة لزيارة العقدة:
- اجتياز غير النظام
- اجتياز الطلب المسبق
- اجتياز الطلب البريدي