پیمایش سطح‌به‌سطح
گره‌های درخت را سطح‌به‌سطح، از بالا به پایین و از چپ به راست، با یک صف ملاقات می‌کند؛ همان BFS روی درخت.
پیمایش‌های پیش‌ترتیب، میان‌ترتیب و پس‌ترتیب عمقیاند: تا ته یک شاخه می‌روند. پیمایش سطح‌به‌سطح اول همه‌ی گره‌های عمق ۰، بعد عمق ۱، بعد عمق ۲ و ... را ملاقات می‌کند.
ادامه‌ی توضیح ↓- زمان:
O(n) - حافظه:
O(n) - هوروویتز–ساهنی، فصل ۵
- جانسون‌باو، فصل ۹
همان درخت پیمایش‌های عمقی؛ خروجی ۱۵، ۶، ۱۸، ۳، ۷، ۱۷، ۲۰ است: سطح‌به‌سطح.
from collections import dequeclass Node:def __init__(self, key):self.key = keyself.left = Noneself.right = Nonedef level_order(root):out = []if root is None:return outqueue = deque([root])while queue:node = queue.popleft()out.append(node.key)if node.left is not None:queue.append(node.left)if node.right is not None:queue.append(node.right)return out
شروع اجرا
متغیرهای محلی
نارنجی = در همین گام عوض شد
root object
- key = 15
- left = Node(key=6, left=Node(key=3, left=None, right=None), right=Node(key=7, left=None, right=None))
- right = Node(key=18, left=Node(key=17, left=None, right=None), right=Node(key=20, left=None, right=None))
Call stack
- level_order()خط 11
رشد تعداد عملیات با اندازه‌ی ورودی
میانگین ۸ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.
- visit
- ورودی فعلی (n=7)
نمایش به شکل جدول
| n | visit |
|---|---|
| 3 | 3 |
| 5 | 5 |
| 7 | 7 |
| 9 | 9 |
| 11 | 11 |
| 13 | 13 |
| 15 | 15 |
توضیح
ایده
پیمایش‌های پیش‌ترتیب، میان‌ترتیب و پس‌ترتیب عمقیاند: تا ته یک شاخه می‌روند. پیمایش سطح‌به‌سطح اول همه‌ی گره‌های عمق ۰، بعد عمق ۱، بعد عمق ۲ و ... را ملاقات می‌کند.
الگوریتم
یک صف (اول‌وارد، اول‌خارج):
- ریشه را در صف بگذار.
- تا صف خالی نشده: گره‌ی اول صف را بردار، ملاقاتش کن و فرزندان چپ و راستش را به ته صف اضافه کن.
این همان BFS روی گراف است؛ چون درخت دور ندارد، نیازی به علامت‌گذاری «دیده‌شده» نیست.
هزینه
هر گره یک بار وارد و یک بار خارج صف می‌شود: O(n). صف حداکثر به اندازه‌ی پهن‌ترین سطح بزرگ می‌شود.
در trace به چه چیزی نگاه کنی
- گره‌های ملاقات‌شده پررنگ می‌شوند؛ صف در پنل حافظه است.