books depth search first
If you do not find what you're looking for, you can use more accurate words.
بحث العمق أولا (Info)
يشار إلى هذا البحث ببحث العمق أولا (DFS)، حيث يُمسح كل ابن لشجرة البحث قدر الإمكان (تعميق المسح) قبل الانتقال إلى الأخ التالي. بالنسبة للشجرة الثنائية، يكون البحث عن طريق العرض العَوْدِي على كل رأس، بدءًا من الجذر، وتكون خوارزميتها كالتالي:
النمط العودية العام لعبور (اجتياز) شجرة ثنائية (غير فارغة) هو:
عند الرأس N قم بالآتي:
(L) امسح عَوْدِيًا شجيرتها الفرعية اليسرى. تنتهي هذه الخطوة في الرأس N مرة أخرى.
(R) امسح عَوْدِيًا شجيرتها الفرعية اليمنى. تنتهي هذه الخطوة في الرأس N مرة أخرى.
(N)تقوم بالعملية على نفسها.
يمكن القيام بهذه الخطوات بأي ترتيب. إذا نُفذت (L) قبل (R)، فستسمى العملية مسح من اليسار إلى اليمين، وإن كان العكس تسمى مسح من اليمين إلى اليسار. تُظهر الطرق التالية عملية مسح من اليسار إلى اليمين:
ترتيب السابق (NLR)
- تحقق مما إذ كان الرأس الحالي فارغًا أو خاليًا.
- عرض بيانات الجذر (أو الرأس الحالي).
- مسح الشجرة الفرعية اليسرى عن طريق استدعاء عَوْدِي لدالة الترتيب المسبق.
- مسح الشجرة الفرعية اليمنى عن طريق استدعاء عَوْدِي لدالة الترتيب المسبق.
مسح الترتيب المسبق هو مسح مرتب طوبولوجيا، حيث يمسح الرأس الأب قبل أبنائه.
في الترتيب (LNR)
- تحقق مما إذ كانت الرأس الحالي فارغًا أو خاليًا.
- مسح الشجرة الفرعية اليسرى عن طريق استدعاء عَوْدِي لدالة في الترتيب.
- عرض بيانات الجذر (أو الرأس الحالي).
- امسح الشجرة الفرعية اليمنى عن طريق استدعاء عَوْدِي لدالة في الترتيب.
في شجرة البحث الثنائية، يُظهر مسح في الترتيب بيانات الشجرة بطريقة مرتبة تصاعديا.
خارج الترتيب (RNL)
- تحقق مما إذ كانت الرأس الحالي فارغًا أو خاليًا.
- امسح الشجرة الفرعية اليمنى عن طريق استدعاء عَوْدِي لدالة خارج الترتيب.
- عرض بيانات الجذر (أو الرأس الحالي).
- مسح الشجرة الفرعية اليسرى عن طريق استدعاء عَوْدِي لدالة خارج الترتيب.
في شجرة البحث الثنائية، يُظهر مسح في الترتيب بيانات الشجرة بطريقة مرتبة تنازليا.
الترتيب اللاحق (LRN)
- تحقق مما إذ كانت الرأس الحالي فارغًا أو خاليًا.
- مسح الشجرة الفرعية اليسرى عن طريق استدعاء عَوْدِي لدالة بعد الترتيب.
- امسح الشجرة الفرعية اليمنى عن طريق استدعاء عَوْدِي لدالة بعد الترتيب.
- عرض بيانات الجذر (أو الرأس الحالي).
مسار مسح بنية الشجرة عبارة عن سَلْسَلَة للشجرة. وهو قائمة متسلسلة للرؤوس المجتازة. ليس هناك سَلْسَلَة قائمة على الترتيب السابق أو اللاحق تصف الشجرة الأصلية وصفا دقيقًا وفريدًا. في حالة شجرة ذات عناصر مختلفة، فيمكن استعمال إما الترتيب اللاحق أو السابق مقرونين بدالة في الترتيب، للحصول على سَلْسَلَة تصف الشجرة الأصلية بدقة وبشكل فريد. ومع ذلك، فإن الترتيب السابق واللاحق يتركان بعض الغموض في بنية الشجرة.
بنية شجرة من أي نوع
لمسح أي شجرة من خلال بحث «العمق أولا»، نفذ العمليات التالية عَوْديًا على كل رأس شجرة:
- نفذ عملية الترتيب السابق.
- لكل ط من 1 إلى عدد الأبناء قم بما يلي:
- زيارة الرأس ط، إذا كان موجودا.
- نفذ عملية في الترتيب.
- نفذ عملية الترتيب اللاحق.
اعتمادًا على المشكلة المطروحة، قد لا تستعمل واحدة من العمليات السابقة، أو قد ترغب في زياة ابن محدد، لذلك قد تكون هذه العمليات اختيارية. أيضًا، في الممارسة العملية، قد تكون هناك حاجة إلى أكثر من واحدة من العمليات السابقة، على سبيل المثال، عند الإدراج في شجرة ثلاثية، يتم تنفيذ عملية ترتيب سابق بمقارنة العناصر. قد تكون هناك حاجة لعملية الترتيب اللاحف لإعادة التوازن إلى الشجرة.
