كتب أنواع المسح

على عكس القوائم المتسلسلة، والمصفوفات أحادية البعد وغيرها من هياكل البيانات الخطية، والتي تُمسح (تجتاز) ببساطة وبترتيب خطي، قد تُمسح الأشجار بطرق متعددة. فقد تمسح بترتيب «العرض أولا» أو «العمق أولا». هناك ثلاث طرق شائعة لعبورها بترتيب العمق أولا وهي كالتالي: ترتيب، ترتيب مسبق، ترتيب لاحق. إلى جانب طرق العبور الأساسية هذه، توجد مخططات أكثر تعقيدًا أو هجينة، مثل عمليات البحث محدودة العمق أو مثل البحث التكراري بالعمق المتعمق الأول.

هياكل البيانات لمسح الشجرة

مسح شجرة ينطوي على تتابع العبور على جميع الرؤوس بطريقة ما. نظرًا لوجود أكثر من رأس ابن واحد محتمل من رأس ما (ليست بنية بيانات خطية)، إذن، بافتراض حوسبة متسلسلة (وليس موازية)، يجب تأجيل بعض الرؤوس - تُخزن بطريقة ما للزيارة لاحقا. تخزن غالبًا عبر مكدس (LIFO) أو طابور (FIFO). نظرًا لأن الشجرة عبارة عن بنية بيانات ذات مرجعية ذاتية (محددة عوديا)، يمكن إجراء المسح عوديا أو، بشكل أكثر دقة، مزدوج العودية، بطريقة سهلة وواضحة للغاية ؛ في هذه الحالات، تخزن ضمنيًا الرؤوس المؤجلة في مكدس الاستدعاءات.

يمكن تطبيق بحث «العمق أولا» بسهولة عبر بنية المكدس، بما في ذلك عوديا (عبر مكدس الاستدعاءات)، في حين يُنفذ بحث «العرض أولا» بسهولة عبر بنية الطابور، بما في ذلك بشكل متزامن.

بحث العمق أولا

يشار إلى هذا البحث ببحث العمق أولا (DFS)، حيث يُمسح كل ابن لشجرة البحث قدر الإمكان (تعميق المسح) قبل الانتقال إلى الأخ التالي. بالنسبة للشجرة الثنائية، يكون البحث عن طريق العرض العَوْدِي على كل رأس، بدءًا من الجذر، وتكون خوارزميتها كالتالي:

النمط العودية العام لعبور (اجتياز) شجرة ثنائية (غير فارغة) هو:

عند الرأس N قم بالآتي:

(L) امسح عَوْدِيًا شجيرتها الفرعية اليسرى. تنتهي هذه الخطوة في الرأس N مرة أخرى.

(R) امسح عَوْدِيًا شجيرتها الفرعية اليمنى. تنتهي هذه الخطوة في الرأس N مرة أخرى.

(N)تقوم بالعملية على نفسها.

يمكن القيام بهذه الخطوات بأي ترتيب. إذا نُفذت (L) قبل (R)، فستسمى العملية مسح من اليسار إلى اليمين، وإن كان العكس تسمى مسح من اليمين إلى اليسار. تُظهر الطرق التالية عملية مسح من اليسار إلى اليمين:

ترتيب السابق (NLR)

1. تحقق مما إذ كان الرأس الحالي فارغًا أو خاليًا.
2. عرض بيانات الجذر (أو الرأس الحالي).
3. مسح الشجرة الفرعية اليسرى عن طريق استدعاء عَوْدِي لدالة الترتيب المسبق.
4. مسح الشجرة الفرعية اليمنى عن طريق استدعاء عَوْدِي لدالة الترتيب المسبق.

مسح الترتيب المسبق هو مسح مرتب طوبولوجيا، حيث يمسح الرأس الأب قبل أبنائه.

في الترتيب (LNR)

1. تحقق مما إذ كانت الرأس الحالي فارغًا أو خاليًا.
2. مسح الشجرة الفرعية اليسرى عن طريق استدعاء عَوْدِي لدالة في الترتيب.
3. عرض بيانات الجذر (أو الرأس الحالي).
4. امسح الشجرة الفرعية اليمنى عن طريق استدعاء عَوْدِي لدالة في الترتيب.

في شجرة البحث الثنائية، يُظهر مسح في الترتيب بيانات الشجرة بطريقة مرتبة تصاعديا.

خارج الترتيب (RNL)

1. تحقق مما إذ كانت الرأس الحالي فارغًا أو خاليًا.
2. امسح الشجرة الفرعية اليمنى عن طريق استدعاء عَوْدِي لدالة خارج الترتيب.
3. عرض بيانات الجذر (أو الرأس الحالي).
4. مسح الشجرة الفرعية اليسرى عن طريق استدعاء عَوْدِي لدالة خارج الترتيب.

في شجرة البحث الثنائية، يُظهر مسح في الترتيب بيانات الشجرة بطريقة مرتبة تنازليا.

الترتيب اللاحق (LRN)

1. تحقق مما إذ كانت الرأس الحالي فارغًا أو خاليًا.
2. مسح الشجرة الفرعية اليسرى عن طريق استدعاء عَوْدِي لدالة بعد الترتيب.
3. امسح الشجرة الفرعية اليمنى عن طريق استدعاء عَوْدِي لدالة بعد الترتيب.
4. عرض بيانات الجذر (أو الرأس الحالي).

مسار مسح بنية الشجرة عبارة عن سَلْسَلَة للشجرة. وهو قائمة متسلسلة للرؤوس المجتازة. ليس هناك سَلْسَلَة قائمة على الترتيب السابق أو اللاحق تصف الشجرة الأصلية وصفا دقيقًا وفريدًا. في حالة شجرة ذات عناصر مختلفة، فيمكن استعمال إما الترتيب اللاحق أو السابق مقرونين بدالة في الترتيب، للحصول على سَلْسَلَة تصف الشجرة الأصلية بدقة وبشكل فريد. ومع ذلك، فإن الترتيب السابق واللاحق يتركان بعض الغموض في بنية الشجرة.

بنية شجرة من أي نوع

لمسح أي شجرة من خلال بحث «العمق أولا»، نفذ العمليات التالية عَوْديًا على كل رأس شجرة:

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

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

بحث «العرض أولا»

يمكن أيضًا مسح بنى الأشجار بترتيب مستوى، حيث نزور كل رأس في المستوى الحالي قبل الانتقال إلى المستوى الأدنى. يشار إلى هذا البحث باسم بحث «العرض أولا»، حيث مسح شجرة البحث بالعرض قدر عرضها في كل عمق قبل الانتقال إلى العمق التالي.

أنواع أخرى

هناك أيضًا خوارزميات مسح بنية الأشجار التي تُصنف على أنها لا بحث «العمق أولا» ولا بحث «العرض أولا». إحدى هذه الخوارزميات هي شجرة بحث مونت كارلو، والذي يركز على تحليل التحركات المتوقعة، معتمدا على تمديد شجرة البحث بأخذ عينات عشوائية من مساحة البحث.