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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

تطبيقات المسح 

يمكن مضاعفة شجرة ثنائية عن طريق مسح ذو ترتيب سابق بمضاعفة الرؤوس والأطراف (الأوراق)، وتُستعمل أيضا لعمل عبارة بادئة (التدوين البولندي) من شجرة التحليل ومسحها بترتيب سابق. على سبيل المثال مسح بترتيب سابق للشجرة الموضحة في الشكل أعلاه يُنتج "5 4 + 3 2 - 1 * +".

يشيع استخدام مسح في الترتيب على أشجار البحث الثنائية لأنه يُرجع قِيّم الشجرة الأصلية مرتبة، حسب المقارن الذي على أساسه بنيت شجرة البحث الثنائية (وفقا لاسمها).

يمكن تحرير أو حذف شجرة ثنائية بأكملها عن طريق المسح بالترتيب اللاحق وذلك بحذف وتحرير الرؤوس وقيمها. يمكنه أيضا إنتاج تمثيل لاحق لشجرة ثنائية، مسح بترتيب لاحق للشجرة الموضحة في الشكل أعلاه يُنتج "+ 5 4 * - 3 2 1".

تطبيق عملي

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

ترتيب سابق

بالترتيب

ترتيب لاحق 

تتطلب الإجراءات السابقة مكدس به مساحة كافية لطول الشجرة والذي يسمى بمكدس الإستدعاء في حالة الإجراء العودي وبالمكدس الأب في حالة الحلقات التكرارية.

في شجرة متوازنة، يجب الأخذ بعين الاعتبار عند استعمال الإجراءات التكرارية أنه يمكننا إزالة متطلبات المكدس من خلال الحفاظ على المؤشرات الرئيسية في كل رأس، أو عن طريق نظم الشجرة (القسم الآتي).

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

مزايا:

 يتجنب العودية واستخدامها لمكدس الإستدعاء واستهلاكها للذاكرة والوقت.
 يحتفظ الرأس بسجل عن الرأس الأب.

سلبيات:

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

مسح موريس هو تحقيق لمسح بالترتيب يستخدم الخيوط: 

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

بحث العرض أولًا 
تماما كما سبق التالي عبارة عن شبه شفرة لمسح بسيط حسب ترتيب المستويات وعن طريق طابور. والذي سيحتاج إلى مساحة كافية لأكبر عدد ممكن من الرؤوس عند عمق معين. حيث تساوي هذه المساحة نصف عدد الرؤوس. يمكن تطبيق نهج أكثر كفاءة في استخدام المساحة لهذا النوع من التطبيق باستخدام بحث تعميق العمق أولا بالتكرار.
 المستوى (الجذر)
 q ← طابور فارغ
 q.enqueue (الجذر)
 بينما (وليس q.isEmpty ())
 العقدة ← q.dequeue ()
 زيارة (عقدة)
 إذا (node.left ≠ خالية)
 q.enqueue (node.left)
 إذا (node.right ull null)
 q.enqueue (node.right)

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

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

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

يمكن تقديم تحليل أكثر تطوراً لوقت التشغيل عبر الأرقام الترتيبية اللانهائية؛ على سبيل المثال، سيتخذ بحث العرض لشجرة العمق 2 أعلاه خطوات ω · 2: ω للمستوى الأول، ثم ω للمستوى الثاني.

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

بشكل ملموس، بالنظر إلى شجرة المتفرعة بلا حدود من العمق اللانهائي، قم بتسمية الجذر ()، أبناء الجذر (1)، (2)... أحفاد (1، 1)، (1، 2)... (2)، 1)، (2، 2)... وهلم جرا. العقد هي بالتالي في واحد إلى واحد مراسلات مع تسلسل محدود (ربما فارغة) من أرقام موجبة، والتي هي قابل للعد ويمكن وضعها في الدرجة الأولى من مجموع الإدخالات، ومن ثم من قبل النظام lexicographic ضمن مبلغ معين (إلا بشكل محدود تُلخص العديد من التسلسلات بقيمة معينة، وبالتالي يتم الوصول إلى جميع المدخلات - هناك عددًا محدودًا من التراكيب ذات العدد الطبيعي المحدد، وتحديداً التراكيب 2 n − 1 من )، والتي تعطي اجتيازًا. صراحة:
 0: ()
 1: (1)
 2: (1، 1) (2)
 3: (1، 1، 1) (1، 2) (2، 1) (3)
 4: (1، 1، 1، 1) (1، 1، 2) (1، 2، 1) (1، 3) (2، 1، 1) (2، 2) (3، 1) (4) 
إلخ

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

المراجع 

 عامة

 ديل، نيل. ليلي، سوزان د. «هياكل بيانات باسكال بلس». العاصمة هيث وشركاه. ليكسينغتون، ماساتشوستس. عام 1995. طبعة رابعة.
 دروزديك، آدم. «هياكل البيانات والخوارزميات في C ++». بروك / كول. باسيفيك جروف، كاليفورنيا عام 2001. الطبعة الثانية.
 http://www.math.northwestern.edu/~mlerma/courses/cs310-05s/notes/dm-treetran

روابط خارجية 

 تخزين البيانات الهرمية في قاعدة بيانات مع أمثلة اجتياز في PHP
 إدارة البيانات الهرمية في MySQL
 العمل مع الرسوم البيانية في الخلية
 رمز عينة لاجتياز شجرة تكرارية وتكرارية مطبق في C.
 رمز عينة لاجتياز شجرة العودية في C #.
 انظر اجتياز شجرة تنفيذها في لغة البرمجة المختلفة على رمز رشيد
 اجتياز شجرة دون العودية

أشجار (بنى معطيات)
استدعاء ذاتي
تكرار في برمجة
خوارزميات مخططات
علم الحاسوب
في علم الحاسوب ، يُمثل مسح ( اجتياز ) الشجرة ( المعروف أيضًا ب اسم البحث في الشجرة وبالإنجليزية tree traversal ) شكلًا من أشكال مسح الرسم البياني و يشير إلى عملية زيارة ( فحص و / أو تحديث ) كل عقدة في هيكلة الشجرة للبايانات ، مرة واحدة ب الضبط . تختلف أنواع المسح حسب ترتيب زيارة رؤوس الشجرة . الخوارزميات التالية خاصة ببنية الشجرة الثنائية ، و لٰكن قد تُعمم على هياكل الأشجار الأخرى أيضًا . أنواع المسح على عكس القوائم المت سلسلة ، والمصفوفات أحادية البعد و غير ها من هياكل البيانات الخطية ، و التي تُمسح ( تجتاز ) ببساطة وبترتيب خطي ، قد تُمسح الأشجار ب طرق متعددة . ف قد تمسح ب ترتيب « العرض أولا » أو « العمق أولا » . هناك ثلاث طرق شائعة لعبور ها ب ترتيب العمق أولا و هي ك التالي : ترتيب ، ترتيب مسبق ، ترتيب لاحق . إلى جانب طرق العبور الأساسية هذه ، توجد مخططات أكثر تعقيدًا أو هجينة ، مثل عمليات البحث محدودة العمق أو مثل البحث التكرار ي ب العمق المتعمق الأول . هياكل البيانات لمسح الشجرة مسح شجرة ينطوي على تتابع العبور على جميع ال رؤوس ب طريقة ما . نظرًا ل وجود أكثر من رأس ابن واحد محتمل من رأس ما ( ليست بنية بيانات خطية ) ، إذن ، بافتراض حوسبة مت سلسلة ( و ليس موازية ) ، يجب تأجيل بعض ال رؤوس - تُخزن ب طريقة ما ل الزيارة لاحقا . تخزن غالبًا عبر مكدس ( L IFO ) أو طابور ( F IFO ) . نظرًا لأن الشجرة عبارة عن بنية بيانات ذات مرجعية ذاتية ( محددة عوديا ) ، يمكن إجراء المسح عوديا أو ، ب شكل أكثر دقة ، مزدوج العودية ، ب طريقة سهلة و واضحة ل الغاية ؛ في هذه الحالات ، تخزن ضمنيًا ال رؤوس المؤجلة في مكدس ال استدعاءات . يمكن تطبيق بحث « العمق أولا » ب سهولة عبر بنية المكدس ، ب ما في ذلك عوديا ( عبر مكدس ال استدعاءات ) ، في حين يُنفذ بحث « العرض أولا » ب سهولة عبر بنية الطابور ، ب ما في ذلك ب شكل متزامن . بحث العمق أولا يشار إلى هذا البحث ب بحث العمق أولا ( DFS ) ، حيث يُمسح كل ابن لشجرة البحث قدر ال إمكان ( تعميق المسح ) قبل الانتقال إلى الأخ التالي . ب النسبة للشجرة الثنائية ، يكون البحث عن طريق العرض العَوْدِي على كل رأس ، بدءًا من الجذر ، و تكون خوارزمية ها ك التالي : النمط العودية العام لعبور ( اجتياز ) شجرة ثنائية ( غير فارغة ) هو : عند الرأس N قم ب الآتي : ( L ) امسح عَوْدِيًا شجيرة ها الفرعية ال يسرى . تنتهي هذه الخطوة في الرأس N مرة أخرى . ( R ) امسح عَوْدِيًا شجيرة ها الفرعية اليمنى . تنتهي هذه الخطوة في الرأس N مرة أخرى . ( N ) تقوم بالعملية على نفس ها . يمكن القيام ب هٰذه الخطوات ب أي ترتيب . إذا نُفذت ( L ) قبل ( R ) ، فستسمى العملية مسح من اليسار إلى اليمين ، و إن كان العكس تسمى مسح من اليمين إلى اليسار . تُظهر الطرق التالية عملية مسح من اليسار إلى اليمين : ترتيب السابق ( NLR ) تحقق مما إذ كان الرأس الحالي فارغًا أو خاليًا . عرض بيانات الجذر ( أو الرأس الحالي ) . مسح الشجرة الفرعية ال يسرى عن طريق استدعاء عَوْدِي لدالة الترتيب المسبق . مسح الشجرة الفرعية اليمنى عن طريق استدعاء عَوْدِي لدالة الترتيب المسبق . مسح الترتيب المسبق هو مسح مرتب طوبولوجيا ، حيث يمسح الرأس الأب قبل أبناء ه . في الترتيب ( LNR ) تحقق مما إذ كانت الرأس الحالي فارغًا أو خاليًا . مسح الشجرة الفرعية ال يسرى عن طريق استدعاء عَوْدِي لدالة في الترتيب . عرض بيانات الجذر ( أو الرأس الحالي ) . امسح الشجرة الفرعية اليمنى عن طريق استدعاء عَوْدِي لدالة في الترتيب . في شجرة البحث الثنائية ، يُظهر مسح في الترتيب بيانات الشجرة ب طريقة مرتبة تصاعديا . خارج الترتيب ( RNL ) تحقق مما إذ كانت الرأس الحالي فارغًا أو خاليًا . امسح الشجرة الفرعية اليمنى عن طريق استدعاء عَوْدِي لدالة خارج الترتيب . عرض بيانات الجذر ( أو الرأس الحالي ) . مسح الشجرة الفرعية ال يسرى عن طريق استدعاء عَوْدِي لدالة خارج الترتيب . في شجرة البحث الثنائية ، يُظهر مسح في الترتيب بيانات الشجرة ب طريقة مرتبة تنازليا . الترتيب اللاحق ( LRN ) تحقق مما إذ كانت الرأس الحالي فارغًا أو خاليًا . مسح الشجرة الفرعية ال يسرى عن طريق استدعاء عَوْدِي لدالة بعد الترتيب . امسح الشجرة الفرعية اليمنى عن طريق استدعاء عَوْدِي لدالة بعد الترتيب . عرض بيانات الجذر ( أو الرأس الحالي ) . مسار مسح بنية الشجرة عبارة عن سَلْسَلَة للشجرة . و هو قائمة مت سلسلة لل رؤوس المجتازة . ليس هناك سَلْسَلَة قائمة على الترتيب السابق أو اللاحق تصف الشجرة الأصلية وصفا دقيقًا وفريدًا . في حالة شجرة ذات عناصر مختلفة ، ف يمكن استعمال إما الترتيب اللاحق أو السابق مقرونين بدالة في الترتيب ، ل الحصول على سَلْسَلَة تصف الشجرة الأصلية ب دقة و ب شكل فريد . و مع ذلك ، ف إن الترتيب السابق واللاحق يتركان بعض الغموض في بنية الشجرة . بنية شجرة من أي نوع لمسح أي شجرة من خلال بحث « العمق أولا » ، نفذ العمليات التالية عَوْديًا على كل رأس شجرة : نفذ عملية الترتيب السابق . ل كل ط من إلى عدد الأبناء قم ب ما يلي : زيارة الرأس ط ، إذا كان موجودا . نفذ عملية في الترتيب . نفذ عملية الترتيب اللاحق . اعتمادًا على المشكلة المطروحة ، قد لا تس تعمل واحدة من العمليات السابقة ، أو قد ترغب في زياة ابن محدد ، ل ذٰلك قد تكون هذه العمليات اختيارية . أيضًا ، في ال ممارسة العملية ، قد تكون هناك حاجة إلى أكثر من واحدة من العمليات السابقة ، على سبيل المثال ، عند ال إدراج في شجرة ثلاثية ، يتم تنفيذ عملية ترتيب سابق بمقارنة العناصر . قد تكون هناك حاجة ل عملية الترتيب اللاحف ل إعادة التوازن إلى الشجرة . بحث « العرض أولا » يمكن أيضًا مسح بنى الأشجار ب ترتيب مستوى ، حيث نزور كل رأس في المستوى الحالي قبل الانتقال إلى المستوى الأدنى . يشار إلى هذا البحث ب اسم بحث « العرض أولا » ، حيث مسح شجرة البحث بالعرض قدر عرض ها في كل عمق قبل الانتقال إلى العمق التالي . أنواع أخرى هناك أيضًا خوارزميات مسح بنية الأشجار التي تُصنف على أن ها لا بحث « العمق أولا » و لا بحث « العرض أولا » . إحدى هذه الخوارزميات هي شجرة بحث مونت كارلو ، و الذي يركز على تحليل التحركات المتوقعة ، معتمدا على تمديد شجرة البحث ب أخذ عينات عشوائية من مساحة البحث . تطبيقات المسح يمكن مضاعفة شجرة ثنائية عن طريق مسح ذو ترتيب سابق ب مضاعفة ال رؤوس و الأطراف ( الأوراق ) ، وتُس تعمل أيضا ل عمل عبارة بادئة ( التدوين البولندي ) من شجرة ال تحليل ومسح ها ب ترتيب سابق . على سبيل المثال مسح ب ترتيب سابق للشجرة الموضحة في الشكل أعلا ه يُنتج " 5 + 2 - * + " . يشيع استخدام مسح في الترتيب على أشجار البحث الثنائية لأن ه يُرجع قِيّم الشجرة الأصلية مرتبة ، حسب المقارن الذي على أساس ه بنيت شجرة البحث الثنائية ( وفقا لاسم ها ) . يمكن تحرير أو حذف شجرة ثنائية ب أكمل ها عن طريق المسح ب الترتيب اللاحق و ذٰلك بحذف وتحرير ال رؤوس وقيم ها . يمكن ه أيضا إنتاج تمثيل لاحق لشجرة ثنائية ، مسح ب ترتيب لاحق للشجرة الموضحة في الشكل أعلا ه يُنتج " + 4 * - 2 . تطبيق عمل ي بحث العمق أولا ترتيب سابق ب الترتيب ترتيب لاحق تتطلب الإجراءات السابقة مكدس ب ه مساحة كافية لطول الشجرة و الذي يسمى بمكدس الإستدعاء في حالة الإجراء العودي وبالمكدس الأب في حالة الحلقات التكرارية . في شجرة متوازنة ، يجب الأخذ ب عين الاعتبار عند استعمال الإجراءات التكرارية أن ه يمكن نا إزالة متطلبات المكدس من خلال الحفاظ على المؤشرات الرئيسية في كل رأس ، أو عن طريق نظم الشجرة ( القسم الآتي ) . مسح ب الترتيب لموريس ب استعمال التشعب ( شريط ال تعليمات ) يُنفذ الخيط على شجرة ثنائية عن طريق جعل كل مؤشر كل ابن على اليسار ( يمكن أن يكون خاليًا ) ، يشير إلى دالة ب الترتيب السالفة للرأس ( إن وُجدت ) . و كل مؤشر ابن على اليمين ( يمكن أن يكون خاليًا ) ، يشير إلة دالة الترتيب اللاحقة للرأس ( إن وُجدت ) . مزايا : يتجنب العودية و استخدام ها لمكدس الإستدعاء واستهلاك ها للذاكرة و الوقت . يحتفظ الرأس بسجل عن الرأس الأب . سلبيات : الشجرة معقدة أكثر . نستطيع المسح مرة واحدة في وقت واحد . معرض للأخطاء الأخطاء عندما لا يكون كل من الأبناء موجودين و تشير كل من قيم الرأس إلى أبائهم . مسح موريس هو تحقيق لمسح ب الترتيب يستخدم الخيوط : إنشاء روابط لسابقة دالة ب الترتيب . اطبع البيانات ب استخدام هذه الروابط . التراجع عن التغييرات ل استعادة الشجرة الأصلية . بحث العرض أولًا تماما كما سبق التالي عبارة عن شبه شفرة لمسح بسيط حسب ترتيب المستويات و عن طريق طابور . و الذي س يحتاج إلى مساحة كافية ل أكبر عدد ممكن من ال رؤوس عند عمق معين . حيث تساوي هذه المساحة نصف عدد ال رؤوس . يمكن تطبيق نهج أكثر كفاءة في استخدام المساحة ل هٰذا النوع من التطبيق ب استخدام بحث تعميق العمق أولا بال تكرار . المستوى ( الجذر ) q ← طابور فارغ q.enqueue ( الجذر ) بينما ( و ليس q.isEmpty ( ) ) العقدة ← q.dequeue ( ) زيارة ( عقدة ) إذا ( node.left ≠ خالية ) q.enqueue ( node.left ) إذا ( node.right ull null ) q.enqueue ( node.right ) أشجار لانهائية عادة ما يكون المسح على الأشجار محدودة عدد ال رؤوس ( و ب التالي العمق وعامل التّفرع محدودان ) لكن يمكن تطبيق ه أيضا على أشجار غير محدودة ( لانهائية ) . هذا أمر ذو أهمية خاصة في البرمجة الوظائفية ( خاصةً مع التثمين الكسول ) ، حيث يمكن في كثير من الأحيان إعلان هياكل البيانات اللانهائية ب سهولة و العمل مع ها ، على الرغم من عدم تقييم ها ( ب شكل صارم ) ، لأن هذا س يستغرق وقتًا غير محدود . بعض الأشجار المحدودة أكبر من أن تمثل ها ب شكل صريح ، مثل شجرة اللعبة ل الشطرنج أو غو ، و لذا ف من المفيد تحليل ها كما لو كانت غير محدودة . الشرط الأساسي للمسح هو زيارة كل رأس في نهاية المطاف . ب النسبة إلى الأشجار اللانهائية ، غالبًا ما تفشل الخوارزميات البسيطة في ذلك . على سبيل المثال ، في حالة وجود شجرة ثنائية ذات عمق غير محدود ، ف إن بحث العمق أولاً سيذهب في جانب واحد ( عن طريق الجانب الأيسر ) من الشجرة ، و لن يزور الباقي أبدًا ، و من المؤكد أن المسح ب الترتيب اللاحق أو الترتيب السابق لن يزور أية رأس ، لأن ها لم تصل إلى ورقة ( و في الواقع لن تفعل ذلك أبدا ) . على النقيض من ذلك ، ف إن مسح العرض أولا ( ترتيب المستوى ) سيعبر شجرة ثنائية ذات عمق لا متناهٍ دون مشكلة ، و في الواقع سيمسح أي شجرة بعامل تفرع محدد . من ناحية أخرى ، وب النظر إلى شجرة ب عمق يساوي حيث يحتوي الجذر على عدد لا حصر ل ه من الأبناء ، ولكل من هؤلاء الأبناء إبنان ، س يزور بحث العمق أولا جميع ال رؤوس ، ب مجرد اكمال الأحفاد ( أبناء أبناء رأس معين ) ، س يتم الانتقال إلى التالي ( على افتراض أن ه ليس ترتيبًا لاحقًا ، و في هذه الحالة لا يصل إلى الجذر مطلقًا ) . على النقيض من ذلك ، لن يصل بحث العرض أولا إلى الأحفاد ، لأن ه يسعى إلى اكمال الأبناء أولاً . يمكن تقديم تحليل أكثر تطوراً لوقت التشغيل عبر الأرقام الترتيبية اللانهائية ؛ على سبيل المثال ، سيتخذ بحث العرض لشجرة العمقأعلا ه خطوات ω · ω للمستوى الأول ، ثم ω للمستوى الثاني . و ب التالي ، ف إن عمليات البحث البسيطة الأولى أو العميقة الأولى لا تجتاز كل شجرة لا نهائية ، و ليست فعالة في الأشجار الكبيرة جدًا . و مع ذلك ، يمكن ل الطرق الهجينة اجتياز أي شجرة لا حصر ل ها ( قابلة للعد ) ، و ذٰلك ب شكل أساسي عبر وسيطة قطرية ( « قطري » - مزيج من ال رأسي والأفقي - يتوافق مع مزيج من العمق والاتساع ) . ب شكل ملموس ، ب النظر إلى شجرة المتفرعة ب لا حدود من العمق اللانهائي ، قم بتسمية الجذر ( ) ، أبناء الجذر . . أحفاد . . . . وهلم جرا . العقد هي ب التالي في واحد إلى واحد مراسلات مع تسلسل محدود ( ربما فارغة ) من أرقام موجبة ، و التي هي قابل للعد و يمكن وضع ها في الدرجة الأولى من مجموع الإدخالات ، و من ثم من قبل النظام lexicographic ضمن مبلغ معين ( إلا ب شكل محدود تُ لخص العديد من التسلسلات ب قيمة معينة ، و ب التالي يتم الوصول إلى جميع المدخلات - هناك عددًا محدودًا من التراكيب ذات العدد الطبيعي المحدد ، و تحديدا التراكيبn − من ) ، و التي تعطي اجتيازًا . صراحة : ( ) ( 2 ) ( 1، ( 2 ، ( 3 ) ( 1، ( 1 ، ( 1 ، ( 2 ، ( 2 ، ( 3، ( 4 ) إلخ يمكن تفسير ذلك على أن ه تعيين الشجرة الثنائية العمق اللانهائية على هذه الشجرة ثم تطبيق بحث اتساع : استبدل الحواف « السفلية » التي تربط العقدة الرئيسية بأطفال ها الثانيين واللاحقين بأطراف « يمينية » من الطفل الأول إلى الثاني الطفل ، من الطفل الثاني إلى الطفل الثالث ، إلخ . و ب التالي في كل خطوة ، يمكن للمرء إما النزول ( إلحاق ( ، إلى النهاية ) أو الانتقال يمينًا ( إضافة واحد إلى الرقم الأخير ) ( ب استثناء الجذر ، و هو إضافي و يمكن ه فقط ) ، مما يدل على المراسلات بين الشجرة الثنائية اللانهائية والترقيم أعلا ه ؛ مجموع المدخلات ( ناقص واحد ) يتوافق مع المسافة من الجذر ، و التي تتفق مع العقدn − 1 على عمق في الشجرة الثنائية اللانهائية يتوافق مع الثنائية ) . المراجع عامة ديل ، نيل . ليلي ، سوزان د . « هياكل بيانات باسكال بلس » . العاصمة هيث وشركاه . ليكسينغتون ، ماساتشوستس . عام طبعة رابعة . دروزديك ، آدم . « هياكل البيانات والخوارزميات في C + + » . بروك / كول . باسيفيك جروف ، كاليفورنيا عام الطبعة الثانية . http://www.math.northwestern.edu/ ~ m lerma / courses / cs310 - 05s / notes / dm - treetran روابط خارجية تخزين البيانات الهرمية في قاعدة بيانات مع أمثلة اجتياز في PHP إدارة البيانات الهرمية في MySQL العمل مع الرسوم البيانية في الخلية رمز عينة لاجتياز شجرة تكرارية وتكرارية مطبق في C . رمز عينة لاجتياز شجرة العودية في C # . انظر اجتياز شجرة تنفيذ ها في لغة البرمجة المختلفة على رمز رشيد اجتياز شجرة دون العودية أشجار ( بنى معطيات ) استدعاء ذاتي تكرار في برمجة خوارزميات مخططات علم الحاسوب