پیمایش‌های درخت

بازگشتی

پیمایش پیش‌ترتیب، میان‌ترتیب و پس‌ترتیب یک درخت دودویی با بازگشت؛ میان‌ترتیبِ درخت جستجو کلیدها را مرتب می‌دهد.

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

ادامه‌ی توضیح ↓

زمان: O(n)
حافظه: O(h) for the recursion (h = height)
هوروویتز–ساهنی، فصل ۵
CLRS، بخش ۱۲.۱
جانسون‌باو، فصل ۹
گریمالدی، فصل ۱۲

ورودی:

n=7خروجی PDF

درخت جستجوی هفت‌گره‌ای ناکامل؛ سه پیمایش سه ترتیب متفاوت می‌دهند و میان‌ترتیب مرتب است.

class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def traversals(root):
pre = []
preorder(root, pre)
ino = []
inorder(root, ino)
post = []
postorder(root, post)
return pre, ino, post
def preorder(node, out):
if node is None:
return
out.append(node.key)
preorder(node.left, out)
preorder(node.right, out)
def inorder(node, out):
if node is None:
return
inorder(node.left, out)
out.append(node.key)
inorder(node.right, out)
def postorder(node, out):
if node is None:
return
postorder(node.left, out)
postorder(node.right, out)
out.append(node.key)

ناوردا: هر فراخوانی، کل زیردرختِ ریشه‌شده در node را پیمایش می‌کند و فقط بعد از آن برمی‌گردد.

شروع اجرا

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

متغیرهای محلی

نارنجی = در همین گام عوض شد

`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

traversals()خط 8

گام ۱ از ۱۸۵

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۸ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

visit
ورودی فعلی (n=7)

نمایش به شکل جدول

n	visit
3	9
5	15
7	21
9	27
11	33
13	39
15	45

توضیح

ایده

| پیمایش | ترتیب | | --- | --- | | پیش‌ترتیب (preorder) | گره، چپ، راست | | میان‌ترتیب (inorder) | چپ، گره، راست | | پس‌ترتیب (postorder) | چپ، راست، گره |

نکته‌ی مهم: میان‌ترتیب در درخت جستجو

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

کاربردها

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

هزینه

هر گره یک بار دیده می‌شود: O(n). عمق بازگشت برابر ارتفاع درخت است: log n برای درخت متوازن و n برای زنجیر.

در trace به چه چیزی نگاه کنی

گره‌ی نارنجی همان node در فراخوانی جاری است و گره‌های سیاه قبلاً به خروجی اضافه شده‌اند.
لیست out زیر درخت ترتیب دیدن را نشان می‌دهد.
در «درخت فراخوانی‌های بازگشتی»، فراخوانی‌های ∅ همان فرزندهای ناموجودند که بلافاصله برمی‌گردند.
سطح جزئیات «هر دور حلقه» فقط پایان هر سه پیمایش را نشان می‌دهد.