اجتياز الأشجار

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

الأنواع

أ

ب

ج

د

هـ

F

0

طريقة الاجتياز: 1

إعادة تشغيل العقدة السابقة بدء التشغيل

عرض توضيحي تفاعلي لطرق اجتياز الشجرة المختلفة

على عكس القوائم المتصلة والمصفوفات أحادية البعد وغيرها من هياكل البيانات الخطية ، التي تُجتاز عادةً بترتيب خطي، يمكن اجتياز الأشجار بطرق متعددة. يمكن اجتيازها بترتيب البحث العمقي أو البحث العرضي . هناك ثلاث طرق شائعة لاجتيازها بترتيب البحث العمقي: الترتيب الداخلي، والترتيب المسبق، والترتيب اللاحق. ^{[ 1 ]} بالإضافة إلى هذه الطرق الأساسية، توجد مخططات أكثر تعقيدًا أو هجينة، مثل عمليات البحث المحدودة العمق كالبحث العمقي التكراري المتعمق . يمكن استخدام هذا الأخير، بالإضافة إلى البحث العرضي، لاجتياز الأشجار اللانهائية، كما هو موضح أدناه .

هياكل البيانات لاجتياز الأشجار

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

يمكن تنفيذ البحث العميق أولاً بسهولة باستخدام مكدس، بما في ذلك بشكل تكراري (عبر مكدس الاستدعاءات)، بينما يمكن تنفيذ البحث العرضي أولاً بسهولة باستخدام طابور، بما في ذلك بشكل تكراري مشترك. ^{[ 2 ]}^{: 45-61}

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

في البحث العميق أولاً (DFS)، يتم تعميق شجرة البحث قدر الإمكان قبل الانتقال إلى الشقيق التالي.

لاجتياز الأشجار الثنائية باستخدام البحث العميق أولاً، يتم تنفيذ العمليات التالية عند كل عقدة: ^{[ 3 ]}^{[ 4 ]}

إذا كانت العقدة الحالية فارغة، فقم بالعودة.
نفّذ العمليات الثلاث التالية بترتيب معين: ^{[ 5 ]}
ن: قم بزيارة العقدة الحالية.
L: اجتياز الشجرة الفرعية اليسرى للعقدة الحالية بشكل متكرر.
R: اجتياز الشجرة الفرعية اليمنى للعقدة الحالية بشكل متكرر.

يُطلق على مسار اجتياز الشجرة اسم تسلسل الشجرة. مسار الاجتياز عبارة عن قائمة بكل عقدة تمت زيارتها. لا يوجد تسلسل واحد، سواءً كان ترتيبًا مسبقًا أو ترتيبًا وسيطًا أو ترتيبًا لاحقًا، يصف الشجرة الأساسية بشكل فريد. عند وجود شجرة ذات عناصر مميزة، يكفي استخدام الترتيب المسبق أو الترتيب اللاحق مع الترتيب الوسيط لوصف الشجرة بشكل فريد. مع ذلك، فإن استخدام الترتيب المسبق مع الترتيب اللاحق يترك بعض الغموض في بنية الشجرة. ^{[ 6 ]}

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

F - B - A - A - A - B - D - C - C - C - D - E - E - E - D - B - F - G - G - I - H - H - H - I - I - G - F

طلب مسبق، NLR

قم بزيارة العقدة الحالية (في الشكل: الموضع باللون الأحمر).
قم باجتياز الشجرة الفرعية اليسرى للعقدة الحالية بشكل متكرر.
قم باجتياز الشجرة الفرعية اليمنى للعقدة الحالية بشكل متكرر.

إن عملية اجتياز الترتيب المسبق هي عملية مرتبة طوبولوجيًا ، لأنه تتم معالجة العقدة الأصلية قبل معالجة أي من العقد الفرعية التابعة لها.

بعد الطلب، LRN

قم باجتياز الشجرة الفرعية اليسرى للعقدة الحالية بشكل متكرر.
قم باجتياز الشجرة الفرعية اليمنى للعقدة الحالية بشكل متكرر.
قم بزيارة العقدة الحالية (في الشكل: الموضع باللون الأزرق).

يمكن أن يكون اجتياز الترتيب اللاحق مفيدًا للحصول على تعبير لاحق لشجرة تعبير ثنائية .

بالترتيب، LNR

قم باجتياز الشجرة الفرعية اليسرى للعقدة الحالية بشكل متكرر.
قم بزيارة العقدة الحالية (في الشكل: الموضع الأخضر).
قم باجتياز الشجرة الفرعية اليمنى للعقدة الحالية بشكل متكرر.

في شجرة بحث ثنائية مرتبة بحيث يكون المفتاح في كل عقدة أكبر من جميع المفاتيح في شجرتها الفرعية اليسرى وأصغر من جميع المفاتيح في شجرتها الفرعية اليمنى، فإن عملية اجتياز الترتيب الداخلي تسترجع المفاتيح بترتيب تصاعدي . ^{[ 7 ]}

إلغاء الطلب المسبق، دوري الرجبي الوطني

قم بزيارة العقدة الحالية.
قم باجتياز الشجرة الفرعية اليمنى للعقدة الحالية بشكل متكرر.
قم باجتياز الشجرة الفرعية اليسرى للعقدة الحالية بشكل متكرر.

إعادة ترتيب ما بعد المعالجة، RLN

قم باجتياز الشجرة الفرعية اليمنى للعقدة الحالية بشكل متكرر.
قم باجتياز الشجرة الفرعية اليسرى للعقدة الحالية بشكل متكرر.
قم بزيارة العقدة الحالية.

الترتيب العكسي، RNL

قم باجتياز الشجرة الفرعية اليمنى للعقدة الحالية بشكل متكرر.
قم بزيارة العقدة الحالية.
قم باجتياز الشجرة الفرعية اليسرى للعقدة الحالية بشكل متكرر.

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

الأشجار العشوائية

لاجتياز الأشجار العشوائية (ليس بالضرورة الأشجار الثنائية) باستخدام البحث العميق أولاً، يتم تنفيذ العمليات التالية عند كل عقدة:

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

بحسب طبيعة المشكلة المطروحة، قد تكون عمليات الترتيب المسبق والترتيب اللاحق، وخاصةً عملية الترتيب الداخلي (عدد الأشجار الفرعية - 1)، اختيارية. وفي الواقع العملي، قد يتطلب الأمر أكثر من عملية واحدة من عمليات الترتيب المسبق والترتيب اللاحق والترتيب الداخلي. على سبيل المثال، عند إدراج عنصر في شجرة ثلاثية، تُجرى عملية الترتيب المسبق بمقارنة العناصر. وقد يلزم إجراء عملية الترتيب اللاحق لاحقًا لإعادة توازن الشجرة.

البحث بالعرض أولاً

في البحث بالعرض أولاً (BFS) أو البحث بترتيب المستوى ، يتم توسيع شجرة البحث قدر الإمكان قبل الانتقال إلى العمق التالي.

أنواع أخرى

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

التطبيقات

يمكن استخدام الترتيب المسبق لإنشاء تعبير بادئ ( بالتدوين البولندي ) من أشجار التعبير : يتم اجتياز شجرة التعبير بترتيب مسبق. على سبيل المثال، ينتج عن اجتياز التعبير الحسابي الموضح بترتيب مسبق "+ * A − BC + DE " . في التدوين البادئ، لا حاجة للأقواس طالما أن لكل عامل عدد ثابت من المعاملات. يُستخدم الترتيب المسبق أيضًا لإنشاء نسخة من الشجرة.

يمكن لخوارزمية اجتياز ما بعد الترتيب توليد تمثيل لاحق ( ترميز بولندي عكسي ) لشجرة ثنائية. ينتج عن اجتياز التعبير الحسابي الموضح بترتيب ما بعد الترتيب " ABC − * DE ++ "؛ ويمكن تحويل هذا الأخير بسهولة إلى لغة الآلة لتقييم التعبير بواسطة آلة المكدس . تُستخدم خوارزمية اجتياز ما بعد الترتيب أيضًا لحذف الشجرة، حيث يتم تحرير كل عقدة بعد تحرير أبنائها.

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

التطبيقات

تطبيق البحث العميق أولاً

فيما يلي أمثلة على التنفيذ القائم على المكدس لاجتياز الترتيب المسبق والترتيب اللاحق والترتيب الداخلي في النهج التكراري (يسار) وكذلك النهج التكراري (يمين).

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

كما تم ذكر العديد من التطبيقات البديلة.

تنفيذ الطلب المسبق

الإجراء preorder(node) إذا كان node = null إرجاع زيارة (العقدة) preorder(node.left) preorder(node.right)

الإجراء iterativePreorder(node) إذا كان node = null، فأرجع stack ← مكدس فارغ stack.push(node) بينما لا تكون المكدسة فارغة node ← stack.pop() زيارة (العقدة) // يتم دفع العنصر الأيمن أولاً حتى تتم معالجة العنصر الأيسر أولاً إذا كان node.right ≠ null stack.push(node.right) إذا كان `node.left` يساوي `null`، فأضفه إلى المكدس.

تنفيذ ما بعد الطلب

الإجراء postorder(node) إذا كان node = null إرجاع postorder(node.left) postorder(node.right) زيارة (العقدة)

الإجراء iterativePostorder(node) إذا كانت node = null، فأرجع stack ← مكدس فارغ، lastNodeVisited ← null، طالما أن stack.isEmpty() ليس فارغًا أو node ≠ null ، إذا كانت node ≠ null stack.push(node) node ← node.left آخر peekNode ← stack.peek() // إذا كان الابن الأيمن موجودًا ويجتاز العقدة // من الطفل الأيسر، ثم انتقل إلى اليمين إذا كان peekNode.right ≠ null و lastNodeVisited ≠ peekNode.right node ← peekNode.right آخر زيارة (peekNode) lastNodeVisited ← stack.pop()

التنفيذ حسب الترتيب

الإجراء inorder(node) إذا كان node = null إرجاع inorder(node.left) زيارة (العقدة) inorder(node.right)

الإجراء iterativeInorder(node) إذا كان node = null ، فأرجع stack ← مكدسًا فارغًا طالما أن stack.isEmpty() ليس فارغًا أو node ≠ null إذا كان node ≠ null stack.push(node) node ← node.left آخر node ← stack.pop() زيارة (العقدة) node ← node.right

نوع آخر من الطلب المسبق

إذا تم تمثيل الشجرة بواسطة مصفوفة (الفهرس الأول هو 0)، فمن الممكن حساب فهرس العنصر التالي: ^{[ 8 ]}

الإجراء bubbleUp(المصفوفة، i، الورقة) k ← 1 i ← (i - 1)/2 بينما (الورقة + 1) % (ك * 2) ≠ ك i ← (i - 1)/2 k ← 2 * k أعد i الإجراء preorder(المصفوفة) i ← 0 بينما i ≠ حجم المصفوفة زيارة(المصفوفة[i]) إذا كان i = الحجم - 1 أنا ← الحجم وإلا إذا كان i < size/2 i ← i * 2 + 1 آخر ورقة ← i - الحجم/2 parent ← bubble_up(array, i, leaf) i ← parent * 2 + 2

الانتقال إلى العقدة التالية أو السابقة

ربما تم العثور على العنصر nodeالذي يجب البدء به في شجرة البحث الثنائية bstعن طريق وظيفة بحث قياسية ، والتي تظهر هنا في تطبيق بدون مؤشرات الأصل، أي أنها تستخدم عنصرًا stackلحفظ مؤشرات الأسلاف.

إجراء البحث (bst، المفتاح) // يُرجع (عقدة، مكدس) node ← bst.root المكدس ← مكدس فارغ طالما أن العقدة ≠ فارغة stack.push(node) إذا كان المفتاح يساوي مفتاح العقدة، فأرجع (العقدة، المكدس). إذا كان المفتاح أقل من مفتاح العقدة node ← node.left آخر node ← node.right إرجاع ( لا شيء ، مكدس فارغ )

تقوم الدالة inorderNext ^{[ 2 ]}^{: 60} بإرجاع جار مرتب لـ node، إما اللاحق المرتب (لـ dir=1) أو السابق المرتب (لـ dir=0)، و ، stackبحيث يمكن اجتياز شجرة البحث الثنائية بشكل متسلسل والبحث فيها في الاتجاه المحدد dirلاحقًا .

الإجراء inorderNext(node, dir, stack) newnode ← node.child[dir] إذا كانت العقدة الجديدة لا تساوي فارغة، فقم بما يلي: عقدة ← عقدة جديدة stack.push(node) newnode ← node.child[1-dir] حتى يصبح newnode = null، أعد (node، stack) // العقدة ليس لها مجلد فرعي: إذا كانت المكدسة فارغة، فأرجع ( null ، مكدسة فارغة ) . العقدة القديمة ← العقدة node ← stack.pop() // الأصل للعقدة القديمة حتى يصبح oldnode ≠ node.child[dir] // الآن oldnode = node.child[1-dir], // أي أن العقدة = سلف (والسابق/اللاحق) للعقدة الأصلية return (node, stack)

لاحظ أن الدالة لا تستخدم مفاتيح، مما يعني أن البنية التسلسلية تُسجل بالكامل بواسطة حواف شجرة البحث الثنائية. بالنسبة لعمليات الاجتياز دون تغيير الاتجاه، يكون متوسط التعقيد ( المُستهلك ) هو ${\mathcal {O}}(1)،$ لأن عملية العبور الكاملة تستغرق $2n-2$ خطوات لإنشاء شجرة بحث ثنائية بحجم $n,$ خطوة واحدة للصعود من الحافة وخطوة واحدة للأسفل. أما تعقيد الحالة الأسوأ فهو ${\mathcal {O}}(h)$ مع $h$ بارتفاع الشجرة.

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

اجتياز موريس بالترتيب الداخلي باستخدام الخيوط

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

المزايا:

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

العيوب:

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

اجتياز موريس هو تطبيق لاجتياز الترتيب الداخلي الذي يستخدم الخيوط: ^{[ 9 ]}

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

البحث بالعرض أولاً

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

إجراء levelorder(node) قائمة الانتظار ← قائمة انتظار فارغة queue.enqueue(node) بينما لا تكون قائمة الانتظار فارغة node ← queue.dequeue() زيارة (العقدة) إذا كان node.left ≠ null queue.enqueue(node.left) إذا كان node.right لا يساوي null، فقم بإضافة node.right إلى قائمة الانتظار.

إذا تم تمثيل الشجرة بواسطة مصفوفة (الفهرس الأول هو 0)، يكفي المرور عبر جميع العناصر:

الإجراء levelorder(array) for i from 0 to array.size زيارة(المصفوفة[i])

أشجار لا حصر لها

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

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

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

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

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

بصورةٍ ملموسة، بالنظر إلى شجرة متفرعة بلا حدود ذات عمق لا نهائي، نُسمّي الجذر ()، وأبناء الجذر (1)، (2)، ...، وأحفاده (1، 1)، (1، 2)، ...، (2، 1)، (2، 2)، ...، وهكذا. بالتالي، تُقابل العُقد تطابقًا تامًا مع متواليات محدودة (قد تكون فارغة) من الأعداد الموجبة، وهي قابلة للعد ويمكن ترتيبها أولًا حسب مجموع عناصرها، ثم حسب الترتيب المعجمي ضمن مجموع مُعطى (عدد محدود فقط من المتواليات يُساوي مجموعها قيمة مُعطاة، لذا يتم الوصول إلى جميع العناصر - رسميًا، يوجد عدد محدود من تركيبات عدد طبيعي مُعطى، تحديدًا 2 ^{^n - 1} تركيبًا لـ n ≥ 1 )، مما يُعطي مسارًا.

()
(1)
(1، 1) (2)
(1، 1، 1) (1، 2) (2، 1) (3)
(1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)

إلخ.

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

مراجع

↑ "المحاضرة 8، اجتياز الشجرة" . تم الاطلاع عليه في 2 مايو 2015 .
1 2 بفاف، بن (2004). مقدمة في أشجار البحث الثنائية والأشجار المتوازنة . مؤسسة البرمجيات الحرة.
↑ طرق اجتياز الشجرة الثنائية
↑ "خوارزمية اجتياز الترتيب المسبق" . تم الاطلاع عليها في 2 مايو 2015 .
يشير الرمز ↑ L قبل R إلى المرور (القياسي) عكس اتجاه عقارب الساعة، كما هو موضح في الشكل.يحدد تنفيذ N قبل أو بين أو بعد L وR إحدى الطرق الموصوفة.إذا تم المرور في الاتجاه المعاكس (مع عقارب الساعة)، يُسمى المرور معكوسًا. يُشرح هذا بالتفصيل في حالة المرور العكسي بالترتيب ، عندما تُسترجع البيانات بترتيب تنازلي.
↑ "الخوارزميات، ما هي تركيبات التسلسل المسبق واللاحق والتسلسل الداخلي الفريدة؟، موقع تبادل المعلومات في علوم الحاسوب" . تم الاطلاع عليه في 2 مايو 2015 .
↑ ويتمان، تود. "اجتياز الشجرة" (ملف PDF) . قسم الرياضيات بجامعة كاليفورنيا في لوس أنجلوس . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 13 فبراير 2015. تم الاطلاع عليه بتاريخ 2 يناير 2016 .
↑ "هياكل شجرة constexpr" . مدونة فقير . 9 أغسطس 2021. تم الاطلاع عليه بتاريخ 15 أغسطس 2021 .
↑ موريس، جوزيف م. (1979). "اجتياز الأشجار الثنائية ببساطة وبتكلفة منخفضة". رسائل معالجة المعلومات . 9 (5): 197-200 . doi : 10.1016/0020-0190(79)90068-1 .

مصادر

ديل، نيل. ليلي، سوزان د. "باسكال بلس: هياكل البيانات". شركة دي سي هيث. ليكسينغتون، ماساتشوستس. 1995. الطبعة الرابعة.
دروزديك، آدم. "هياكل البيانات والخوارزميات في لغة C++". بروك/كول. باسيفيك غروف، كاليفورنيا. 2001. الطبعة الثانية.
"التحليل العرضي للشجرة" (math.northwestern.edu)

روابط خارجية

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

[holtenotes-1] "المحاضرة 8، اجتياز الشجرة" . تم الاطلاع عليه في 2 مايو 2015 .

[Pfaff-2] 1 2 بفاف، بن (2004). مقدمة في أشجار البحث الثنائية والأشجار المتوازنة . مؤسسة البرمجيات الحرة.

[3] طرق اجتياز الشجرة الثنائية

[4] "خوارزمية اجتياز الترتيب المسبق" . تم الاطلاع عليها في 2 مايو 2015 .

[5] يشير الرمز ↑ L قبل R إلى المرور (القياسي) عكس اتجاه عقارب الساعة، كما هو موضح في الشكل.يحدد تنفيذ N قبل أو بين أو بعد L وR إحدى الطرق الموصوفة.إذا تم المرور في الاتجاه المعاكس (مع عقارب الساعة)، يُسمى المرور معكوسًا. يُشرح هذا بالتفصيل في حالة المرور العكسي بالترتيب ، عندما تُسترجع البيانات بترتيب تنازلي.

[6] "الخوارزميات، ما هي تركيبات التسلسل المسبق واللاحق والتسلسل الداخلي الفريدة؟، موقع تبادل المعلومات في علوم الحاسوب" . تم الاطلاع عليه في 2 مايو 2015 .

[7] ويتمان، تود. "اجتياز الشجرة" (ملف PDF) . قسم الرياضيات بجامعة كاليفورنيا في لوس أنجلوس . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 13 فبراير 2015. تم الاطلاع عليه بتاريخ 2 يناير 2016 .

[8] "هياكل شجرة constexpr" . مدونة فقير . 9 أغسطس 2021. تم الاطلاع عليه بتاريخ 15 أغسطس 2021 .

[9] موريس، جوزيف م. (1979). "اجتياز الأشجار الثنائية ببساطة وبتكلفة منخفضة". رسائل معالجة المعلومات . 9 (5): 197-200 . doi : 10.1016/0020-0190(79)90068-1 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]