خوارزميةاحترافي
اجتياز الشجرة بالعمق
زُر شجرة بحث ثنائية بالترتيب: الشجرة الفرعية اليسرى، ثم العقدة، ثم الشجرة الفرعية اليمنى.
- الزمن
- O(n)
- الذاكرة
- O(h)
تتبّعها خطوة بخطوة
الخطوة 1 من 14
1function inorder(node, out) {2 if (node === null) return;3 inorder(node.left, out);4 out.push(node.val);5 inorder(node.right, out);6}- out
- = []
- 4
- 2
- 6
- 1
- 3
- 5
- 7
عند 4: ندخل الشجرة الفرعية اليسرى أولاً.
درس احترافي
افتح الشرح الكامل
هذا الدرس جزء من الخطة الاحترافية، التي تفتح كل خطوة في كل درس، إضافة إلى تدريبات الأنماط وتقارير الإتقان.
اطّلع على الأسعاركيف تعمل
البحث بالعمق يتعمّق قدر الإمكان قبل أن يرجع. والاجتياز المرتّب (in-order) يفعل ذلك بترتيب ثابت: الشجرة الفرعية اليسرى كاملة، ثم العقدة نفسها، ثم الشجرة الفرعية اليمنى. العَوْدية تتكفّل بالرجوع تلقائياً، لأن كل استدعاء يعود إلى العقدة الأم. في شجرة البحث الثنائية يُخرج هذا الترتيب القيم مرتّبة. تُزار كل عقدة مرة واحدة: الزمن O(n)، والذاكرة O(h) لمكدّس الاستدعاءات، حيث h ارتفاع الشجرة.
تدرّب على اكتشاف هذا النمط →