در این فصل چه یاد میگیری#
فصلِ قبل از ریشه به پایین راه رفت و به یک برگ رسید. این فصل میخواهد همهٔ گرهها را ببیند — و معلوم میشود «همه» یک کار نیست، چهار کار است.
چهار پیمایش میسازیم و روی درختِ ۸٬۱۹۱ گرهای امتحانشان میکنیم. هر چهارتا دقیقاً 8,191 گره را میبینند، پس از نظرِ مرتبه هیچ فرقی ندارند. ولی چیزی که همزمان در حافظه نگه میدارند خیلی فرق دارد: یکی حداکثر 13 گره و دیگری 4,096 گره. آخرِ فصل هم RecursionError فصلِ قبل را با یک stack صریح از میان برمیداریم.

آخر این فصل میتوانی:
pre-order،in-order،post-orderوlevel-orderرا روی یک درختِ کوچک با دست بنویسی- یک پیمایش را با
stackصریح، بدونِrecursion، پیاده کنی - هزینهٔ حافظهٔ پیمایشِ
stackی و پیمایشِqueueای را از هم جدا کنی، با عدد - بگویی چرا دو کدِ تقریباً یکسان دو ترتیبِ متفاوت میدهند
قبل از شروع#
از فصلِ ۱: گره با سه خانه، درختِ کامل، زنجیر، و اینکه recursion روی زنجیر میشکند.
از ترمِ ۲ فصلِ ۷: stack و queue، و popleft در برابرِ pop(0). این فصل همان دو انضباط را روی یک درخت میگذارد و میبینی که فقط ترتیبِ بازدید عوض میشود.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. سه ترتیب، از یک الگوی واحد#
روی هر گره سه کار انجام میشود: خودِ گره، زیردرختِ چپ، زیردرختِ راست. هر سه پیمایشی که با recursion نوشته میشوند دقیقاً همین سه خط را دارند و فقط جای خطِ اول عوض میشود.
pre-order: اول خودِ گرهin-order: خودِ گره وسطِ دو زیردرختpost-order: خودِ گره آخر از همه
VALUE, LEFT, RIGHT = 0, 1, 2
def perfect(h, value=1):
"""همان درختِ کاملِ فصلِ قبل: هر گره یا دو فرزند دارد یا هیچ."""
if h < 0:
return None
return [value, perfect(h - 1, 2 * value), perfect(h - 1, 2 * value + 1)]
def chain(n):
"""n گره که هر کدام فقط یک فرزندِ چپ دارد."""
node = None
for v in range(n, 0, -1):
node = [v, node, None]
return node
def pre_order(node, out=None):
"""اول خودِ گره، بعد زیردرختِ چپ، بعد زیردرختِ راست."""
if out is None:
out = []
if node is not None:
out.append(node[VALUE])
pre_order(node[LEFT], out)
pre_order(node[RIGHT], out)
return out
def in_order(node, out=None):
"""اول زیردرختِ چپ، بعد خودِ گره، بعد زیردرختِ راست."""
if out is None:
out = []
if node is not None:
in_order(node[LEFT], out)
out.append(node[VALUE])
in_order(node[RIGHT], out)
return out
def post_order(node, out=None):
"""اول هر دو زیردرخت، آخر از همه خودِ گره."""
if out is None:
out = []
if node is not None:
post_order(node[LEFT], out)
post_order(node[RIGHT], out)
out.append(node[VALUE])
return out
small = perfect(2)
print("درخت :", small)
print("pre-order :", pre_order(small))
print("in-order :", in_order(small))
print("post-order:", post_order(small))
درخت : [1, [2, [4, None, None], [5, None, None]], [3, [6, None, None], [7, None, None]]]
pre-order : [1, 2, 4, 5, 3, 6, 7]
in-order : [4, 2, 5, 1, 6, 3, 7]
post-order: [4, 5, 2, 6, 7, 3, 1]
سه سطرِ خروجی را با دست دنبال کن؛ همین یک بار کافی است تا دیگر هیچوقت جایشان را عوض نکنی.
pre-order با ریشه شروع میشود، post-order با ریشه تمام میشود، و in-order ریشه را دقیقاً وسط میگذارد — سه گره قبلش، سه گره بعدش. هر سه ترتیب همان هفت عدد را دارند و فقط چیدمانشان فرق میکند.
کجا بهدردت میخورد: post-order وقتی لازم است که تا زیردرختها تمام نشدهاند نتوانی دربارهٔ گره تصمیم بگیری — دقیقاً مثلِ تابعِ height فصلِ قبل، که یک post-order بود بدونِ اینکه اسمش را برده باشیم. و in-order تا فصلِ بعد فقط یک ترتیبِ عجیب است؛ آنجا معلوم میشود چرا مهمترینشان است.
۲. ترتیبِ چهارم: سطح به سطح#
سه ترتیبِ بالا همه با recursion ساخته شدند و همهشان عمق را ترجیح میدهند: تا ته یک شاخه میروند و بعد برمیگردند. ترتیبِ چهارم برعکس است — اول همهٔ گرههای سطحِ یک، بعد همهٔ سطحِ دو. این را با recursion نمیشود بهسادگی نوشت، ولی با یک queue سه خط است.
from collections import deque
def level_order(node):
"""سطح به سطح: هر گرهای که بیرون میآید، فرزندانش ته صف میروند."""
out = []
if node is None:
return out
waiting = deque([node])
while waiting:
current = waiting.popleft()
out.append(current[VALUE])
if current[LEFT] is not None:
waiting.append(current[LEFT])
if current[RIGHT] is not None:
waiting.append(current[RIGHT])
return out
print("level-order:", level_order(small))
print("هر چهار ترتیب همان هفت گره را دارند؟",
sorted(pre_order(small)) == sorted(in_order(small))
== sorted(post_order(small)) == sorted(level_order(small)))
level-order: [1, 2, 3, 4, 5, 6, 7]
هر چهار ترتیب همان هفت گره را دارند؟ True
level-order روی این درخت دقیقاً 1 تا 7 را مرتب چاپ کرد — که اتفاقی نیست: تابعِ perfect به هر فرزند شمارهٔ 2 * value و 2 * value + 1 میدهد، و همین شمارهگذاری یعنی سطح به سطح از چپ به راست. در فصلِ ۴ همین شمارهگذاری تبدیل به کلِ ایدهٔ heap میشود.
۳. همان pre-order، بدونِ recursion#
recursion در واقع یک stack است که پایتون برایت نگه میدارد. اگر خودت آن stack را بسازی، همان کار را بدونِ سقفِ call stack انجام میدهی.
تنها نکتهاش ترتیبِ گذاشتن است: stack آخرین چیز را اول برمیدارد، پس اگر میخواهی چپ زودتر بیرون بیاید، باید راست را اول بگذاری.
def pre_order_stack(node):
"""همان pre-order، با یک stack صریح بهجای recursion."""
out = []
if node is None:
return out
pending = [node]
while pending:
current = pending.pop()
out.append(current[VALUE])
if current[RIGHT] is not None:
pending.append(current[RIGHT])
if current[LEFT] is not None:
pending.append(current[LEFT])
return out
print("با recursion:", pre_order(small))
print("با stack :", pre_order_stack(small))
print("دو نسخه یک جواب میدهند؟", pre_order(small) == pre_order_stack(small))
با recursion: [1, 2, 4, 5, 3, 6, 7]
با stack : [1, 2, 4, 5, 3, 6, 7]
دو نسخه یک جواب میدهند؟ True
سطرِ سوم اختیاری نیست. بازنویسیِ یک الگوریتم بدونِ مقایسهٔ خروجی، بازنویسی نیست؛ نوشتنِ کدِ دیگری است که ممکن است جوابِ دیگری بدهد. و اینجا آن خطر کاملاً واقعی است:
def wrong_push_order(node):
"""همان کد، فقط چپ و راست جابهجا push شدهاند."""
out = []
pending = [node]
while pending:
current = pending.pop()
out.append(current[VALUE])
if current[LEFT] is not None:
pending.append(current[LEFT])
if current[RIGHT] is not None:
pending.append(current[RIGHT])
return out
print("درست :", pre_order_stack(small))
print("معیوب:", wrong_push_order(small))
print("هر دو همهٔ گرهها را دیدهاند؟",
sorted(wrong_push_order(small)) == sorted(pre_order_stack(small)))
درست : [1, 2, 4, 5, 3, 6, 7]
معیوب: [1, 3, 7, 6, 2, 5, 4]
هر دو همهٔ گرهها را دیدهاند؟ True
⚠️ مواظب باش: دو خطِ جابهجا، هیچ خطایی، و ترتیبِ کاملاً غلط. سطرِ آخر بدترین بخشِ ماجراست: هر دو نسخه هر هفت گره را دیدهاند، پس هر آزمونی که فقط «همه را دیدی؟» بپرسد سبز میشود. تنها آزمونی که این را میگیرد، مقایسهٔ خودِ ترتیب است.
۴. هزینه: همه یک تعداد گره میبینند#
🤔 اول حدس بزن: با دو برابر شدنِ تعدادِ گرهها، تعدادِ گرههایی که یک پیمایش بازدید میکند چند برابر میشود؟ بنویسش، بعد جدول را ببین.
forest = {}
for h in (9, 10, 11, 12):
tree = perfect(h)
forest[len(pre_order(tree))] = tree
NODES = sorted(forest)
print("هر چهار پیمایش روی بزرگترین درخت یک تعداد گره میبینند؟",
len(pre_order(forest[NODES[-1]])) == len(in_order(forest[NODES[-1]]))
== len(post_order(forest[NODES[-1]])) == len(level_order(forest[NODES[-1]])))
table([(n, len(pre_order_stack(forest[n]))) for n in NODES], "گرهٔ بازدیدشده", ",d")
هر چهار پیمایش روی بزرگترین درخت یک تعداد گره میبینند؟ True
n گرهٔ بازدیدشده نسبت به سطر قبل
1,023 1,023 —
2,047 2,047 2.00
4,095 4,095 2.00
8,191 8,191 2.00
ستونِ نسبت دقیقاً 2.00 است: پیمایشِ کاملِ درخت O(n) است، برای هر چهار ترتیب. منطقش هم ساده است — هر گره دقیقاً یک بار دیده میشود، نه بیشتر و نه کمتر. پس اگر انتخابِ بینِ این چهارتا فقط بر اساسِ زمان بود، انتخاب معنایی نداشت.
۵. جایی که واقعاً فرق میکنند: حافظه#
سه پیمایشِ اولِ این فصل یک stack نگه میدارند و level-order یک queue. بزرگترین اندازهای که هر کدام در طولِ کار به آن میرسند، هزینهٔ حافظهٔ آن پیمایش است.
🤔 اول حدس بزن: روی درختِ کاملِ ۸٬۱۹۱ گرهای،
stackحداکثر چند گره را همزمان نگه میدارد وqueueچند تا؟ هر دو عدد را بنویس — این حدسزدنیترین جدولِ فصل است.
def peak_stack(node):
"""بیشترین چیزی که pre-orderِ stackی همزمان نگه میدارد."""
peak = 0
pending = [node]
while pending:
peak = max(peak, len(pending))
current = pending.pop()
if current[RIGHT] is not None:
pending.append(current[RIGHT])
if current[LEFT] is not None:
pending.append(current[LEFT])
return peak
def peak_queue(node):
"""بیشترین چیزی که level-order همزمان نگه میدارد."""
peak = 0
waiting = deque([node])
while waiting:
peak = max(peak, len(waiting))
current = waiting.popleft()
if current[LEFT] is not None:
waiting.append(current[LEFT])
if current[RIGHT] is not None:
waiting.append(current[RIGHT])
return peak
print("— pre-order با stack: بیشینهٔ اندازهٔ stack")
table([(n, peak_stack(forest[n])) for n in NODES], "بیشینهٔ stack", ",d")
print("\n— level-order: بیشینهٔ اندازهٔ queue")
table([(n, peak_queue(forest[n])) for n in NODES], "بیشینهٔ queue", ",d")
— pre-order با stack: بیشینهٔ اندازهٔ stack
n بیشینهٔ stack نسبت به سطر قبل
1,023 10 —
2,047 11 1.10
4,095 12 1.09
8,191 13 1.08
— level-order: بیشینهٔ اندازهٔ queue
n بیشینهٔ queue نسبت به سطر قبل
1,023 512 —
2,047 1,024 2.00
4,095 2,048 2.00
8,191 4,096 2.00
13 در برابرِ 4,096. همان درخت، همان تعدادِ بازدید، و سیصد و پانزده برابر تفاوت در حافظه.
دلیلش را از فصلِ ۱ میشناسی: stack بهاندازهٔ ارتفاعِ درخت بزرگ میشود و queue بهاندازهٔ عرضِ آن. در درختِ کامل ارتفاع log n است و عریضترین سطح نصفِ کلِ گرهها را دارد — و ستونِ نسبت دقیقاً همین را میگوید: 1.08 در برابرِ 2.00.
قاعدهای که از این درمیآید و در فصلهای گراف بارها بهکارت میآید: پیمایشِ stackی ارزانِ حافظه است و پیمایشِ queueای گران. روی درختِ باریک و بلند دقیقاً برعکس میشود، و بخشِ ۶ همان را نشان میدهد.
۶. و همان زنجیرِ فصلِ قبل#
line = chain(2_000)
try:
pre_order(line)
except RecursionError as err:
print(f"با recursion → {type(err).__name__}: {err}")
print("با stack →", len(pre_order_stack(line)), "گره، بدونِ هیچ خطایی")
print("بیشینهٔ stack روی همین زنجیر:", peak_stack(line))
با recursion → RecursionError: maximum recursion depth exceeded
با stack → 2000 گره، بدونِ هیچ خطایی
بیشینهٔ stack روی همین زنجیر: 1
بدهیِ فصلِ قبل پرداخت شد. نسخهای که recursion دارد روی زنجیرِ ۲٬۰۰۰ گرهای میشکند و نسخهٔ stackی همان کار را بدونِ خطا انجام میدهد.
و سطرِ آخر شگفتانگیزترین عددِ فصل است: stack روی این زنجیر هیچوقت از یک عضو بیشتر نشد. چون هر گره فقط یک فرزند دارد، هیچ چیزی برای «بعداً» کنار گذاشته نمیشود. همان ساختاری که recursion را میشکند، برای stack صریح ارزانترین حالتِ ممکن است — و کلِ تفاوت این است که پایتون در call stack علاوه بر گره، کلِ وضعیتِ فراخوانی را هم نگه میدارد.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ چهار پیمایش روی درختِ کاملِ یکسان، با خروجیِ بررسیشده، روی دو سؤال: تعدادِ بازدید و بیشینهٔ حافظهٔ کمکی. در کدام بازهٔ
n؟ ۱٬۰۲۳ تا ۸٬۱۹۱ گره، بهعلاوهٔ یک زنجیرِ ۲٬۰۰۰ گرهای برای آزمونِrecursion. با چند تکرار، و کمینه یا میانگین؟ یک اجرا؛ هر دو عدد شمارشاند و شمارش قطعی است.
✅ چک کن: در
peak_queueبهجایpopleftبنویسpopو جدولِ بخشِ ۵ را دوباره بگیر. بیشینهٔqueueباید از4,096به عددی حولِ13سقوط کند — چون باpopدیگر صف نیست و همانstackاست. و همین آزمایش میگوید تفاوتِ حافظه از خودِ ظرف نمیآید، از انضباطی میآید که رویش گذاشتهای.
🔧 اگر کار نکرد: پرتکرارترین اشتباه در نوشتنِ پیمایشِ
stackی این است که شرطِ خالیبودن را جا بیندازی و باwhile Trueجلو بروی:
try:
pending = [small]
while True:
current = pending.pop()
if current[RIGHT] is not None:
pending.append(current[RIGHT])
if current[LEFT] is not None:
pending.append(current[LEFT])
except IndexError as err:
print(f"{type(err).__name__}: {err}")
IndexError: pop from empty list
پیام صریح است و دقیقاً همان چیزی را میگوید که اتفاق افتاده: درخت تمام شد، stack خالی شد، و کد هنوز دنبالِ گرهٔ بعدی بود. خوبیِ این خطا این است که فوری بلند میشود — بر خلافِ تلهٔ بخشِ ۳ که یک ترتیبِ غلط را بیسروصدا برگرداند.
🤖 از دستیارت بپرس: «چرا
level-orderروی یک درختِ کامل حافظهٔ خیلی بیشتری ازpre-orderمیخواهد؟» بعد جدولِ بخشِ ۵ را جلویش بگذار و بپرس: «روی چه شکلی از درخت این نتیجه برعکس میشود؟» — جوابِ درست باید درختِ باریک و بلند را نام ببرد و بگوید آنجاqueueهیچوقت بزرگ نمیشود.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| traversal | تراوِرسال | پیمایش: دیدنِ همهٔ گرههای یک ساختار، هر کدام یک بار |
pre-order |
پریاُردر | خودِ گره قبل از هر دو زیردرخت |
in-order |
ایناُردر | خودِ گره بینِ دو زیردرخت |
post-order |
پُستاُردر | خودِ گره بعد از هر دو زیردرخت |
level-order |
لِوِلاُردر | سطح به سطح، با یک queue |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
تا اینجا درختهای ما هیچ قاعدهای نداشتند؛ فقط شکل بودند. فصلِ بعد یک قاعدهٔ ساده روی مقدارها میگذارد — کوچکتر به چپ، بزرگتر به راست — و همان in-order بیخاصیتِ بخشِ ۱ ناگهان همهچیز را مرتب بیرون میدهد.
و همانجا بدترین خبرِ این ترم را هم میگیری: اگر کلیدها را از قبل مرتب به این ساختار بدهی، ارتفاعش از 26.4 به 3,999 میرود و میانگینِ مقایسههای جستوجو از 14.99 به 2,000.50.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.