درخت دودویی (Binary Tree)

درخت دودویی و پیمایش‌های سه‌گانه: preorder، inorder و postorder با پیاده‌سازی بازگشتی و کاربرد هرکدام

درخت دودویی چیست؟

درخت دودویی (Binary Tree) درختی است که هر گره حداکثر ۲ فرزند دارد: فرزند چپ و فرزند راست.

class BinaryNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

انواع خاص درخت دودویی

پیمایش‌های سه‌گانه DFS

محل بازدید گره نسبت به پیمایش فرزندان، سه نوع را می‌سازد:

۱. Preorder (ریشه ← چپ ← راست)

اول خود گره، بعد چپ، بعد راست. کاربرد: کپی درخت، سریال‌سازی، پیشوندهای عبارت.

۲. Inorder (چپ ← ریشه ← راست)

اول چپ، بعد خود گره، بعد راست. کاربرد: در BST، خروجی مرتب‌شده است!

۳. Postorder (چپ ← راست ← ریشه)

اول هر دو فرزند، بعد خود گره. کاربرد: حذف درخت (اول فرزندان!)، پسوندهای عبارت، محاسبه فضای دیسک پوشه‌ها.

مثال یکسان، سه خروجی

        1
       / \
      2   3
     / \
    4   5

Preorder:  1, 2, 4, 5, 3
Inorder:   4, 2, 5, 1, 3
Postorder: 4, 5, 2, 3, 1

جدول کاربردها

پیمایشترتیبکاربرد اصلی
Preorderریشه-چپ-راستکپی/سریال‌سازی درخت
Inorderچپ-ریشه-راستخروجی مرتب BST
Postorderچپ-راست-ریشهحذف درخت، محاسبه از پایین
Level-orderسطح به سطحکوتاه‌ترین مسیر، چاپ سطحی
نکته حفظی: نام پیمایش از «جایگاه ریشه» می‌آید — Pre یعنی ریشه اول، In یعنی ریشه وسط، Post یعنی ریشه آخر!

جمع‌بندی

این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.

ابزارهای مرتبط