# فصل ۰۲ — پیمایشِ درخت، با `recursion` و بدونش

<div dir="rtl">

# فصل ۰۲ — پیمایشِ درخت، با `recursion` و بدونش

## در این فصل چه یاد می‌گیری

فصلِ قبل از ریشه به پایین راه رفت و به یک برگ رسید. **این فصل می‌خواهد همهٔ گره‌ها را ببیند** — و معلوم می‌شود «همه» یک کار نیست، چهار کار است.

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

![درختی که چهار مسیرِ رنگی متفاوت روی گره‌هایش کشیده شده و هر مسیر ترتیبِ دیگری دارد](/lesson-assets/t5-s02-tree-traversal/prompt/01-image-four-walks.png)

آخر این فصل می‌توانی:

- `pre-order`، `in-order`، `post-order` و `level-order` را روی یک درختِ کوچک با دست بنویسی
- یک پیمایش را با `stack` صریح، بدونِ `recursion`، پیاده کنی
- **هزینهٔ حافظهٔ پیمایشِ `stack`ی و پیمایشِ `queue`ای را از هم جدا کنی**، با عدد
- بگویی چرا دو کدِ تقریباً یکسان دو ترتیبِ متفاوت می‌دهند

## قبل از شروع

**از فصلِ ۱:** گره با سه خانه، درختِ کامل، زنجیر، و اینکه `recursion` روی زنجیر می‌شکند.

**از ترمِ ۲ فصلِ ۷:** `stack` و `queue`، و `popleft` در برابرِ `pop(0)`. **این فصل همان دو انضباط را روی یک درخت می‌گذارد و می‌بینی که فقط ترتیبِ بازدید عوض می‌شود.**

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | کمتر از یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-5-trees-and-graphs/session-02-tree-traversal.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. سه ترتیب، از یک الگوی واحد

روی هر گره سه کار انجام می‌شود: **خودِ گره**، **زیردرختِ چپ**، **زیردرختِ راست**. هر سه پیمایشی که با `recursion` نوشته می‌شوند دقیقاً همین سه خط را دارند و **فقط جای خطِ اول عوض می‌شود.**

- `pre-order`: اول خودِ گره
- `in-order`: خودِ گره وسطِ دو زیردرخت
- `post-order`: خودِ گره آخر از همه

</div>

```python
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))
```

```text
درخت      : [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]
```

<div dir="rtl">

**سه سطرِ خروجی را با دست دنبال کن؛ همین یک بار کافی است تا دیگر هیچ‌وقت جایشان را عوض نکنی.**

`pre-order` با ریشه شروع می‌شود، `post-order` با ریشه تمام می‌شود، و `in-order` ریشه را دقیقاً وسط می‌گذارد — سه گره قبلش، سه گره بعدش. **هر سه ترتیب همان هفت عدد را دارند و فقط چیدمانشان فرق می‌کند.**

**کجا به‌دردت می‌خورد:** `post-order` وقتی لازم است که تا زیردرخت‌ها تمام نشده‌اند نتوانی دربارهٔ گره تصمیم بگیری — دقیقاً مثلِ تابعِ `height` فصلِ قبل، که یک `post-order` بود بدونِ اینکه اسمش را برده باشیم. **و `in-order` تا فصلِ بعد فقط یک ترتیبِ عجیب است؛ آن‌جا معلوم می‌شود چرا مهم‌ترینشان است.**

## ۲. ترتیبِ چهارم: سطح به سطح

سه ترتیبِ بالا همه با `recursion` ساخته شدند و همه‌شان **عمق** را ترجیح می‌دهند: تا ته یک شاخه می‌روند و بعد برمی‌گردند. ترتیبِ چهارم برعکس است — **اول همهٔ گره‌های سطحِ یک، بعد همهٔ سطحِ دو.** این را با `recursion` نمی‌شود به‌سادگی نوشت، ولی با یک `queue` سه خط است.

</div>

```python
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)))
```

```text
level-order: [1, 2, 3, 4, 5, 6, 7]
هر چهار ترتیب همان هفت گره را دارند؟ True
```

<div dir="rtl">

**`level-order` روی این درخت دقیقاً `1` تا `7` را مرتب چاپ کرد** — که اتفاقی نیست: تابعِ `perfect` به هر فرزند شمارهٔ `2 * value` و `2 * value + 1` می‌دهد، و همین شماره‌گذاری یعنی سطح به سطح از چپ به راست. **در فصلِ ۴ همین شماره‌گذاری تبدیل به کلِ ایدهٔ `heap` می‌شود.**

## ۳. همان `pre-order`، بدونِ `recursion`

`recursion` در واقع یک `stack` است که پایتون برایت نگه می‌دارد. اگر خودت آن `stack` را بسازی، همان کار را بدونِ سقفِ `call stack` انجام می‌دهی.

**تنها نکته‌اش ترتیبِ گذاشتن است:** `stack` آخرین چیز را اول برمی‌دارد، پس اگر می‌خواهی چپ زودتر بیرون بیاید، باید راست را **اول** بگذاری.

</div>

```python
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))
```

```text
با recursion: [1, 2, 4, 5, 3, 6, 7]
با stack    : [1, 2, 4, 5, 3, 6, 7]
دو نسخه یک جواب می‌دهند؟ True
```

<div dir="rtl">

**سطرِ سوم اختیاری نیست.** بازنویسیِ یک الگوریتم بدونِ مقایسهٔ خروجی، بازنویسی نیست؛ نوشتنِ کدِ دیگری است که ممکن است جوابِ دیگری بدهد. و این‌جا آن خطر کاملاً واقعی است:

</div>

```python
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)))
```

```text
درست : [1, 2, 4, 5, 3, 6, 7]
معیوب: [1, 3, 7, 6, 2, 5, 4]
هر دو همهٔ گره‌ها را دیده‌اند؟ True
```

<div dir="rtl">

> ⚠️ **مواظب باش:** دو خطِ جابه‌جا، هیچ خطایی، و **ترتیبِ کاملاً غلط**. سطرِ آخر بدترین بخشِ ماجراست: هر دو نسخه هر هفت گره را دیده‌اند، پس هر آزمونی که فقط «همه را دیدی؟» بپرسد سبز می‌شود. **تنها آزمونی که این را می‌گیرد، مقایسهٔ خودِ ترتیب است.**

## ۴. هزینه: همه یک تعداد گره می‌بینند

> 🤔 **اول حدس بزن:** با دو برابر شدنِ تعدادِ گره‌ها، تعدادِ گره‌هایی که یک پیمایش بازدید می‌کند چند برابر می‌شود؟ **بنویسش**، بعد جدول را ببین.

</div>

```python
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")
```

```text
هر چهار پیمایش روی بزرگ‌ترین درخت یک تعداد گره می‌بینند؟ True
         n    گرهٔ بازدیدشده     نسبت به سطر قبل
     1,023             1,023                   —
     2,047             2,047                2.00
     4,095             4,095                2.00
     8,191             8,191                2.00
```

<div dir="rtl">

**ستونِ نسبت دقیقاً `2.00` است: پیمایشِ کاملِ درخت `O(n)` است، برای هر چهار ترتیب.** منطقش هم ساده است — هر گره دقیقاً یک بار دیده می‌شود، نه بیشتر و نه کمتر. **پس اگر انتخابِ بینِ این چهارتا فقط بر اساسِ زمان بود، انتخاب معنایی نداشت.**

## ۵. جایی که واقعاً فرق می‌کنند: حافظه

سه پیمایشِ اولِ این فصل یک `stack` نگه می‌دارند و `level-order` یک `queue`. **بزرگ‌ترین اندازه‌ای که هر کدام در طولِ کار به آن می‌رسند، هزینهٔ حافظهٔ آن پیمایش است.**

> 🤔 **اول حدس بزن:** روی درختِ کاملِ ۸٬۱۹۱ گره‌ای، `stack` حداکثر چند گره را هم‌زمان نگه می‌دارد و `queue` چند تا؟ **هر دو عدد را بنویس** — این حدس‌زدنی‌ترین جدولِ فصل است.

</div>

```python
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")
```

```text
— 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
```

<div dir="rtl">

**`13` در برابرِ `4,096`.** همان درخت، همان تعدادِ بازدید، و سیصد و پانزده برابر تفاوت در حافظه.

دلیلش را از فصلِ ۱ می‌شناسی: **`stack` به‌اندازهٔ ارتفاعِ درخت بزرگ می‌شود و `queue` به‌اندازهٔ عرضِ آن.** در درختِ کامل ارتفاع `log n` است و عریض‌ترین سطح نصفِ کلِ گره‌ها را دارد — و ستونِ نسبت دقیقاً همین را می‌گوید: `1.08` در برابرِ `2.00`.

**قاعده‌ای که از این درمی‌آید و در فصل‌های گراف بارها به‌کارت می‌آید: پیمایشِ `stack`ی ارزانِ حافظه است و پیمایشِ `queue`ای گران.** روی درختِ باریک و بلند دقیقاً برعکس می‌شود، و بخشِ ۶ همان را نشان می‌دهد.

## ۶. و همان زنجیرِ فصلِ قبل

</div>

```python
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))
```

```text
با recursion → RecursionError: maximum recursion depth exceeded
با stack     → 2000 گره، بدونِ هیچ خطایی
بیشینهٔ stack روی همین زنجیر: 1
```

<div dir="rtl">

**بدهیِ فصلِ قبل پرداخت شد.** نسخه‌ای که `recursion` دارد روی زنجیرِ ۲٬۰۰۰ گره‌ای می‌شکند و نسخهٔ `stack`ی همان کار را بدونِ خطا انجام می‌دهد.

و سطرِ آخر شگفت‌انگیزترین عددِ فصل است: **`stack` روی این زنجیر هیچ‌وقت از یک عضو بیشتر نشد.** چون هر گره فقط یک فرزند دارد، هیچ چیزی برای «بعداً» کنار گذاشته نمی‌شود. **همان ساختاری که `recursion` را می‌شکند، برای `stack` صریح ارزان‌ترین حالتِ ممکن است** — و کلِ تفاوت این است که پایتون در `call stack` علاوه بر گره، کلِ وضعیتِ فراخوانی را هم نگه می‌دارد.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** چهار پیمایش روی درختِ کاملِ یکسان، با خروجیِ بررسی‌شده، روی دو سؤال: تعدادِ بازدید و بیشینهٔ حافظهٔ کمکی. **در کدام بازهٔ `n`؟** ۱٬۰۲۳ تا ۸٬۱۹۱ گره، به‌علاوهٔ یک زنجیرِ ۲٬۰۰۰ گره‌ای برای آزمونِ `recursion`. **با چند تکرار، و کمینه یا میانگین؟** یک اجرا؛ هر دو عدد شمارش‌اند و شمارش قطعی است.

> ✅ **چک کن:** در `peak_queue` به‌جای `popleft` بنویس `pop` و جدولِ بخشِ ۵ را دوباره بگیر. **بیشینهٔ `queue` باید از `4,096` به عددی حولِ `13` سقوط کند** — چون با `pop` دیگر صف نیست و همان `stack` است. **و همین آزمایش می‌گوید تفاوتِ حافظه از خودِ ظرف نمی‌آید، از انضباطی می‌آید که رویش گذاشته‌ای.**

> 🔧 **اگر کار نکرد:** پرتکرارترین اشتباه در نوشتنِ پیمایشِ `stack`ی این است که شرطِ خالی‌بودن را جا بیندازی و با `while True` جلو بروی:

</div>

```python
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}")
```

```text
IndexError: pop from empty list
```

<div dir="rtl">

پیام صریح است و دقیقاً همان چیزی را می‌گوید که اتفاق افتاده: **درخت تمام شد، `stack` خالی شد، و کد هنوز دنبالِ گرهٔ بعدی بود.** خوبیِ این خطا این است که فوری بلند می‌شود — بر خلافِ تلهٔ بخشِ ۳ که یک ترتیبِ غلط را بی‌سروصدا برگرداند.

> 🤖 **از دستیارت بپرس:** «چرا `level-order` روی یک درختِ کامل حافظهٔ خیلی بیشتری از `pre-order` می‌خواهد؟» بعد **جدولِ بخشِ ۵ را جلویش بگذار و بپرس:** «روی چه شکلی از درخت این نتیجه برعکس می‌شود؟» — جوابِ درست باید درختِ باریک و بلند را نام ببرد و بگوید آن‌جا `queue` هیچ‌وقت بزرگ نمی‌شود.

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| traversal | تراوِرسال | پیمایش: دیدنِ همهٔ گره‌های یک ساختار، هر کدام یک بار |
| `pre-order` | پری‌اُردر | خودِ گره قبل از هر دو زیردرخت |
| `in-order` | این‌اُردر | خودِ گره بینِ دو زیردرخت |
| `post-order` | پُست‌اُردر | خودِ گره بعد از هر دو زیردرخت |
| `level-order` | لِوِل‌اُردر | سطح به سطح، با یک `queue` |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا در پیمایشِ `stack`ی باید فرزندِ راست را زودتر از چپ گذاشت؟

**تمرینِ اجباری:** نسخهٔ `stack`یِ `post-order` را بنویس. (راهنمایی: `pre-order` را با ترتیبِ راست-قبل-از-چپ بگیر و جوابش را برعکس کن.) **جوابت را با `post_order`ِ اصلی روی درختِ ۸٬۱۹۱ گره‌ای با `==` بسنج** و بعد `peak_stack` آن را اندازه بگیر. **سؤالِ اصلی: بیشینهٔ `stack`ش با نسخهٔ `pre-order` یکی است یا نه، و چرا؟**

**تمرینِ ستاره‌دار ⭐:** جدولِ بخشِ ۵ را این بار روی **زنجیر** بگیر، برای چهار اندازهٔ دوبرابرشونده. **قبل از اجرا پیش‌بینی کن** ستونِ نسبتِ `stack` و ستونِ نسبتِ `queue` چه عددی می‌دهند. حالا اندازه بگیر و خطای پیش‌بینی‌ات را بنویس. **و سؤالِ آخر: روی زنجیر کدام‌یک از این دو پیمایش گران‌تر است؟** جوابت باید به هر دو جدول اشاره کند، نه فقط یکی.

## در فصل بعد

تا این‌جا درخت‌های ما هیچ **قاعده‌ای** نداشتند؛ فقط شکل بودند. **فصلِ بعد یک قاعدهٔ ساده روی مقدارها می‌گذارد — کوچک‌تر به چپ، بزرگ‌تر به راست — و همان `in-order` بی‌خاصیتِ بخشِ ۱ ناگهان همه‌چیز را مرتب بیرون می‌دهد.**

و همان‌جا بدترین خبرِ این ترم را هم می‌گیری: اگر کلیدها را **از قبل مرتب** به این ساختار بدهی، ارتفاعش از `26.4` به `3,999` می‌رود و میانگینِ مقایسه‌های جست‌وجو از `14.99` به `2,000.50`.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t5/s02-tree-traversal (یادستان, Yaadestan)
