المكتبة العربية لعلوم الحاسوب
مرحباً بالخوارزميات › الأشجار 9 / 19 السابق التالي

تمارين

مراجعة المفاهيم

الأشجار الثنائية الكاملة والممتلئة والتامة

تمثّل المصفوفتان التاليتان شجرتين ثنائيتين بترتيب المستويات، حيث تشير None إلى موضع فارغ:

  • الشجرة A: [1, 2, 3, 4, 5, 6]
  • الشجرة B: [1, 2, 3, None, None, 6, 7]
  1. أي الشجرتين شجرة ثنائية كاملة؟
  2. أي الشجرتين شجرة ثنائية ممتلئة، أي أن كل عقدة غير ورقية لها ابنان؟
  3. هل أي من الشجرتين شجرة ثنائية تامة؟ اشرح السبب لكل شجرة.

الإجابة

  1. الشجرة A شجرة ثنائية كاملة. فمستواها الأدنى فقط غير ممتلئ، وعقد ذلك المستوى تشغل مواضع متتالية من اليسار إلى اليمين. والشجرة B ليست كاملة لأن في المستوى الأدنى مواضع فارغة على اليسار بينما تظهر عقد على اليمين.

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

  3. لا توجد أي من الشجرتين شجرة ثنائية تامة لأن المستوى الأدنى في كل شجرة غير ممتلئ بالكامل.

أوامر الاجتياز الثلاثة للشجرة نفسها

خزّن المصفوفة [1, 2, 3, 4, 5, 6, 7] بترتيب المستويات في شجرة ثنائية كاملة.

  1. ارسم الشجرة.
  2. اكتب متتاليات الاجتياز المسبق والاجتياز الداخلي والاجتياز اللاحق لها.
  3. في متتالية الاجتياز الداخلي، أي أجزاء الشجرة تقابل المتتاليتين الفرعيتين على يسار العقدة الجذرية 1 وعلى يمينها؟

الإجابة

  1. الشجرة هي:

          1
    /   \
   2     3
  / \   / \
 4   5 6   7

  2. الاجتياز المسبق هو 1, 2, 4, 5, 3, 6, 7؛ والاجتياز الداخلي هو 4, 2, 5, 1, 6, 3, 7؛ والاجتياز اللاحق هو 4, 5, 2, 6, 7, 3, 1.

  3. المتتالية 4, 2, 5 على يسار العقدة الجذرية 1 هي الاجتياز الداخلي للشجرة الفرعية اليسرى؛ والمتتالية 6, 3, 7 على يمينها هي الاجتياز الداخلي للشجرة الفرعية اليمنى.

مقارنة شجرتي بحث ثنائيتين

أدرج كل متتالية من المتتاليات التالية من اليسار إلى اليمين في شجرة بحث ثنائية فارغة:

  • المتتالية A: [4, 2, 6, 1, 3, 5, 7]
  • المتتالية B: [1, 2, 3, 4, 5, 6, 7]
  1. لكل شجرة، اكتب العقد التي تُزار عند البحث عن 7.
  2. إذا قيس الارتفاع بعدد الأضلاع من العقدة الجذرية إلى أبعد عقدة ورقية، فما ارتفاع كل شجرة؟
  3. استناداً إلى السؤالين الأولين، هل البحث عن 7 بنفس الكفاءة في الشجرتين؟ اشرح باستخدام شكلي الشجرتين ومساري البحث.

الإجابة

  1. في الشجرة المبنية من المتتالية A، يكون مسار البحث 4 → 6 → 7. وفي الشجرة المبنية من المتتالية B، يكون مسار البحث 1 → 2 → 3 → 4 → 5 → 6 → 7.

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

  3. ليس البحث عن 7 بنفس الكفاءة في الشجرتين. فرتيب الإدراج يغيّر شكل شجرة البحث الثنائية وارتفاعها. ويزور البحث 3 عقد فقط في الشجرة الأولى لكنه يزور العقد السبع كلها في الشجرة الثانية. وكلما زاد ارتفاع الشجرة، زاد عدد العقد التي قد يلزم مقارنتها على طول مسار في أسوأ الحالات.

تمارين برمجية

أقصى عمق لشجرة ثنائية

تُعطى العقدة الجذرية root لشجرة ثنائية. وتحتوي كل عقدة على قيمة صحيحة ومرجعين إلى ابنيها الأيسر والأيمن.

أقصى عمق هو عدد العقد على المسار من العقدة الجذرية إلى أبعد عقدة ورقية. أعد أقصى عمق للشجرة؛ وأقصى عمق لشجرة فارغة هو 0. استخدم التعاود.

تلميحات

  1. يُقاس العمق بعدد العقد في هذا التمرين، لذا فإن شجرة تحتوي على العقدة الجذرية فقط لها أقصى عمق 1
  2. اجعل الدالة التعاودية تعيد أقصى عمق للشجرة الفرعية ذات الجذر عند العقدة الحالية
  3. أعد 0 للعقدة الفارغة؛ وللعقدة غير الفارغة، أعد max(depth(left), depth(right)) + 1

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

اجتياز شجرة ثنائية مستوى بمستوى

بمعطى العقدة الجذرية root لشجرة ثنائية، استخدم طابوراً لزيارة جميع العقد مستوى بمستوى من الأعلى إلى الأسفل ومن اليسار إلى اليمين داخل كل مستوى.

أعد مصفوفة ثنائية الأبعاد: تخزّن المصفوفة الفرعية الأولى قيم مستوى الجذر، وتخزّن الثانية قيم المستوى التالي، وهكذا. وإذا كانت الشجرة فارغة، فأعد مصفوفة فارغة.

تلميحات

  1. يزور الاجتياز حسب المستويات العقد المُدخلة إلى الطابور أولاً، لذا استخدم طابوراً
  2. في بداية كل جولة، تنتمي جميع العقد الموجودة حالياً في الطابور إلى المستوى نفسه
  3. سجّل أولاً طول الطابور، ثم أخرج عدداً من العقد يساوي ذلك الطول بالضبط وأدخل أبناءها إلى الطابور

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

أصغر عنصر من الرتبة k في شجرة بحث ثنائية

تحتوي شجرة بحث ثنائية على n من العقد بقيم متمايزة. وإذا رُتبت جميع قيم العقد من الأصغر إلى الأكبر، رُقّمت مواضعها بدءاً من 1.

بمعطى العقدة الجذرية root وعدد صحيح k يحقق 1 <= k <= n، أعد القيمة الموجودة في الموضع k. واعثر على الإجابة مباشرةً أثناء اجتياز داخلي بدلاً من جمع جميع قيم العقد أولاً.

تلميحات

  1. يزور الاجتياز الداخلي لشجرة البحث الثنائية قيم العقد من الأصغر إلى الأكبر
  2. يعالج الاجتياز الداخلي الشجرة الفرعية اليسرى، ثم العقدة الحالية، ثم الشجرة الفرعية اليمنى؛ وزد العدّاد عند زيارة العقدة الحالية
  3. عندما يصبح العدّاد مساوياً k لأول مرة، تكون قيمة العقدة الحالية هي الإجابة، فلا حاجة إلى مواصلة الاجتياز

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

السابق ملخص التالي الكومة