ما هي الشجرة الثنائية الكاملة؟

يمكن تعريف الشجرة الثنائية الكاملة بأنها شجرة ثنائية حيث تحتوي جميع العقد على 0 أو طفلين. بمعنى آخر، يمكن تعريف الشجرة الثنائية الكاملة بأنها شجرة ثنائية تحتوي جميع العقد فيها على طفلين باستثناء العقد الورقية.

الشجرة أدناه هي شجرة ثنائية كاملة:

الشجرة أعلاه عبارة عن شجرة ثنائية كاملة حيث أن جميع العقد باستثناء العقد الورقية لها طفلان.

نظرية الشجرة الثنائية الكاملة:

اعتبر أن الشجرة الثنائية T شجرة غير فارغة:

• لنفترض أن أكون عقدًا داخلية في شجرة وL لتكون عقدة ورقية في شجرة، فإن عدد العقد الورقية سيكون مساويًا لـ:
  ل = أنا + 1
• إذا كان T يحتوي على I عدد العقد الداخلية وN هو العدد الإجمالي للعقد، فإن إجمالي عدد العقد سيكون مساويًا لـ:
  N = 2I + 1
• إذا كان T يحتوي على 'N' العدد الإجمالي للعقد و'I' هو عدد العقد الداخلية، فإن عدد العقد الداخلية سيكون مساويًا لـ:
  أنا = (ن-1)/2
• إذا كان 'T' يحتوي على 'N' إجمالي عدد العقد، وكان 'L' عبارة عن عدد من العقد الورقية، فإن عدد العقد الورقية سيكون مساويًا لـ:
  ل = (ن+1)/2
• إذا كان 'T' يحتوي على عدد 'L' من العقد الطرفية، فسيكون إجمالي عدد العقد مساويًا لـ:
  N = 2L - 1
• إذا كان 'T' يحتوي على عدد 'L' من العقد الطرفية، وكان 'I' عبارة عن عدد من العقد الداخلية، فإن عدد العقد الداخلية سيكون مساويًا لـ:
  أنا = ل - 1

ما هي الشجرة الثنائية الكاملة؟

يقال إن الشجرة الثنائية هي شجرة ثنائية كاملة عندما تمتلئ جميع المستويات بالكامل باستثناء المستوى الأخير، الذي يتم ملؤه من اليسار.

الشجرة أدناه هي شجرة ثنائية كاملة:

تشبه الشجرة الثنائية الكاملة الشجرة الثنائية الكاملة باستثناء الاختلافين الموضحين أدناه:

• يجب أن يبدأ ملء العقدة الورقية من أقصى الجانب الأيسر.
• ليس من الضروري أن يكون للعقدة الورقية الأخيرة الأخ الصحيح.

دعونا نفهم النقاط المذكورة أعلاه من خلال مثال:

جافا يساوي

خذ بعين الاعتبار الشجرة أدناه:

الشجرة المذكورة أعلاه عبارة عن شجرة ثنائية كاملة، ولكنها ليست شجرة ثنائية كاملة لأن العقدة 6 ليس لها شقيقها الصحيح.

إنشاء شجرة ثنائية كاملة

لنفترض أن لدينا مجموعة من 6 عناصر كما هو موضح أدناه:

تحتوي المصفوفة أعلاه على 6 عناصر، أي 1، 2، 3، 4، 5، 6. فيما يلي الخطوات التي يجب استخدامها لإنشاء شجرة ثنائية كاملة:

الخطوة 1: أولاً، سنختار العنصر الأول من المصفوفة، أي 1، وننشئ عقدة جذر للشجرة. عدد العناصر المتوفرة في المستوى الأول هو 1.

الخطوة 2: الآن، سوف نقوم باختيار العنصرين الثاني والثالث من المصفوفة. احتفظ بالعنصر الثاني والعنصر الثالث من المصفوفة باعتبارهما الابن الأيسر والأيمن للعقدة الجذرية على التوالي كما هو موضح أدناه:

كما نلاحظ أعلاه أن عدد العناصر المتوفرة في المستوى الثاني هو 2.

الخطوه 3: الآن، سوف نختار العنصرين التاليين من المصفوفة، أي 4 و5. احتفظ بهذين العنصرين على يسار ويمين العقدة 2 كما هو موضح أدناه:

كما يمكننا أن نلاحظ أعلاه أن العقدتين 4 و 5 هما الابن الأيسر والأيمن للعقدة 2 على التوالي.

الخطوة 4: الآن، سوف نختار العنصر الأخير من المصفوفة، أي 6، ونحتفظ به باعتباره الابن الأيسر للعقدة 3 كما نعلم أنه في شجرة ثنائية كاملة، يتم ملء العقد من الجانب الأيسر كما هو موضح أدناه:

كما نلاحظ أن المستوى الثاني يحتوي على 3 عناصر.

دعونا نفهم الاختلافات بين الشجرة الثنائية الكاملة والكاملة من خلال الصور.

خوارزمية dfs

1. الشجرة الثنائية الموضحة أدناه ليست شجرة ثنائية كاملة ولا كاملة. إنها ليست شجرة ثنائية كاملة لأن العقدة 3 لديها طفل واحد فقط. كما أنها ليست شجرة ثنائية كاملة حيث يجب ملء العقد من الجانب الأيسر، ولكن العقدة 3 لديها فرع فرعي أيمن وليس لديها فرع فرعي أيسر.
   
2. الشجرة الثنائية، الموضحة أدناه، هي شجرة ثنائية كاملة ولكنها ليست شجرة ثنائية كاملة. إنها شجرة ثنائية كاملة لأن جميع العقد لديها إما 0 أو 2 من الأطفال. إنها ليست شجرة ثنائية كاملة لأن العقدة 3 لا تحتوي على أي أطفال بينما العقدة 2 لها أطفالها ونحن نعلم أنه يجب ملء العقد من الجانب الأيسر في شجرة ثنائية كاملة.
   
3. الشجرة الثنائية الموضحة أدناه هي شجرة ثنائية كاملة ولكنها ليست شجرة ثنائية كاملة. إنها شجرة ثنائية كاملة حيث يتم ترك جميع العقد ممتلئة. إنها ليست شجرة ثنائية كاملة لأن العقدة 2 لديها طفل واحد فقط.
   
4. الشجرة الثنائية الموضحة أدناه هي شجرة ثنائية كاملة وكاملة. إنها شجرة ثنائية كاملة حيث يتم ترك جميع العقد ممتلئة. إنها شجرة ثنائية كاملة حيث أن جميع العقد لديها إما 0 أو 2 أطفال.