پیمایش درخت

در مقایسه با ساختمان داده‌های خطی مانند لیست‌های پیوندی و آرایه یک بعدی که یک روش پیمایش استاندارد دارند؛ ساختارهای درختی می‌توانند در مسیرهای مختلفی پیمایش شوند. برای شروع از ریشه یک درخت دودویی سه گام اصلی وجود دارد که ترتیب انجام آن‌ها نوع پیمایش درختی را مشخص می‌کند. این مراحل عبارتند از: انجام یک عمل در گره فعلی که اشاره به دیدن گره دارد، پیمایش به سمت گره فرزند چپ و پیمایش به سمت گره فرزند راست در برخی از روش‌ها پیمایش شامل تکرار همه گره‌ها می‌شود. چراکه از گره داده شده ممکن است بیش از یک گره بعدی وجود داشته باشد( در این حالت آن ساختمان داده خطی نیست) پس با فرض محاسبهٔ متوالی (نه موازی) بعضی از گره‌ها باید در برخی مسیرها به تعویق بیفتند و برای ملاقات‌های بعدی ذخیره شوند. این کار اغلب بواسطه پشته و از طریق الگوریتم LIFO یا از طریق صف و از طریق الگوریتم FIFO انجام می‌شود. ساختمان داده همانند یک درخت بازگشتی است، پیمایش می‌تواند به عنوان یک بازگشت تعریف شود، در یک مد طبیعی و روشن گره‌های معوق به صورت ضمنی در پشته تماس ذخیره می‌شوند. نامی که به پیمایش‌ها داده می‌شود از ترتیبی که آن‌ها گره‌ها را ملاقات می‌کنند گرفته شده‌است. به بیان ساده‌تر پیشروی به سمت پایین (اول-عمق، فرزند اول سپس نوه، قبل از فرزند دوم ) یا اول-سطح (اول سطح یا عرض، فرزند اول سپس فرزند دوم قبل از نوه) پیمایش‌های اول –عمق بیشتر بر اساس وضعیت عناصر ریشه با توجه به گره‌های موجود در سمت چپ و راست دسته‌بندی شده‌اند. تصور کنید که گره چپ و راست در مکان خود ثابت هستند، پس گره ریشه می‌تواند در طرف چپ گره سمت چپ قرار داده شود(پیمایش پیشوندی) یا اینکه بین گره راست و چپ قرار گیرد(پیمایش میانوندی) یا طرف راست گره سمت راست باشد (پیمایش پسوندی). هیچگونه اختلاف مشابهی در پیمایش اول-سطح که به گره فرزند نسبت داده شده وجود ندارد؛ در نتیجه پیمایش اول-سطح بی ابهام و واضح است. برای طراحی همیشه فرض بر این است که گره‌های سمت چپ بر گره‌های سمت راست مقدم هستند. این مرتب‌سازی می‌تواند تا زمانی که همین ترتیب برای همه روش‌های پیمایش، درنظرگرفته وارونه شود. پیمایش اول‌عمق از طریق پشته به آسانی قابل پیاده‌سازی است، در حالی که اول‌سطح به سادگی از طریق صف قابل پیاده‌سازی است. فراتر از این پیمایش‌ها عمومی طرح‌های پیچیده‌تر و ترکیبی مختلفی نیز قابل پیاده‌سازی است، نظیر جستجوهای عمق محدود (depth- limited)، جستجوی تعمیق تکراری (iterative deepening depth-first). می‌خواهیم با حرکت روی یال‌های یک درخت، همهٔ گره‌های آن را هر کدام یک بار ملاقات کنیم. به این کار پیمایش درخت می‌گویند. بسته به این که کدام عنصر، کی ملاقات شود، پیمایش درخت لیست یا یک ترتیب خطی از عناصر آن درخت به ما می‌دهد. طبیعتاً پیمایش‌های متفاوت ترتیب‌های متفاوتی خواهند داد. دو روش عمقل اول و سطح اول، دو روش معمول پیمایش درخت هستند که بیشتر برای پیمایش درخت دودویی به کار می‌روند.

اول-عمق Depth-first سه نوع پیمایش اول- عمق وجود دارد: پیمایش پیشوندی (Pre-Order)، پیمایش میانوندی (In-Order)، پیمایش پسوندی (Post- order) برای درخت دودویی، آن‌ها در هر گره، با شروع از گره ریشه به عنوان عملیات بازگشتی تعریف شده‌اند که الگوریتم آن‌ها به شرح زیر است: پیمایش پیش‌ترتیب:

1. ریشه را ملاقات کن.
2. زیر درخت چپ را پیمایش کن.
3. زیر درخت راست را پیمایش کن.

پیمایش میان‌ترتیب:

1. زیردرخت چپ را پیمایش کن.
2. ریشه را ملاقات کن.
3. زیردرخت راست را پیمایش کن.

پیمایش پس‌ترتیب:

1. زیر درخت چپ را پیمایش کن.
2. زیر درخت راست را پیمایش کن.
3. ریشه را ملاقات کن.

Print Pre-order traversal of the tree

}(void preOrder(node* r
} (if(r
;"">>cout <<r->> data
;(preOrder(r->left 
(preOrder(r->right 
{
{

iterativePreorder(node)

 parentStack = empty stack
 while (not parentStack.isEmpty() or node ≠ null)
 if (node ≠ null)
 visit(node)
 if (node.right ≠ null) parentStack.push(node.right)
 node = node.left
 else
 node = parentStack.pop()

In-order inorder(node)

 if node == null then return
 inorder(node.left)
 visit(node)
 inorder(node.right)

iterativeInorder(node)

 parentStack = empty stack
 while (not parentStack.isEmpty() or node ≠ null)
 if (node ≠ null)
 parentStack.push(node)
 node = node.left
 else
 node = parentStack.pop()
 visit(node)
 node = node.right

Post-order postorder(node)

 if node == null then return
 postorder(node.left)
 postorder(node.right)
 visit(node)

iterativePostorder(node)

 parentStack = empty stack
 lastnodevisited = null
 while (not parentStack.isEmpty() or node ≠ null)
 if (node ≠ null)
 parentStack.push(node)
 node = node.left
 else
 peeknode = parentStack.peek()
 if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right)
 /* if right child exists AND traversing node from left child, move right */
 node = peeknode.right
 else
 visit(peeknode)
 lastnodevisited = parentStack.pop()
 node = null

هر کدام از این روش‌های پیمایش را می‌توان به دو روش بازگشتی و غیر بازگشتی پیاده‌سازی کرد.

به منظور پیمایش هر درختی در پیمایش اول-عمق، عملیات‌های بازگشتی زیر در هر گره انجام می‌شود: ۱. انجام عمل پیمایش پیشوندی ۲. برای هر i (با i=1 to n) انجام می‌شود: ۱. ملاقات iام، اگر وجود داشته باشد. ۲. انجام عملیات پیمایش میانوندی ۳. انجام عملیات پیمایش پسوندی جایی که n تعداد گره‌های فرزند است، وابسته به مشکلی که وجود دارد عملیات پیمایش پیشوندی، میانوندی و پسوندی ممکن است بی‌اعتبار شوند یا این‌که ممکن است شما بخواهید از یک گره فرزند خاصی بازدید کنید بنابراین این عملیات‌ها اختیاری هستند. همچنین در عمل ممکن است بیش از یک عملیات پیشوندی، میانوندی و پسوندی نیاز باشد. به عنوان مثال زمان وارد شدن به یک درخت سه تایی، یک عملیات پیشوندی بواسطه مقایسه، بخش‌ها انجام شده‌است. ممکن است یک عملیات پسوندی پس از متوازن کردن مجدد درخت نیاز باشد.

درخت‌ها می‌توانند به ترتیب هر سطح پیمایش شوند، به گونه‌ای که همهٔ گره‌ها در یک سطح را ملاقات می‌کنیم، سپس به ترتیب به سطوح پایین‌تر می‌رویم و تمام گره‌های آن‌ها را ملاقات می‌کنیم.

روش‌های پیمایش دیگری هم وجود دارند که جزء هیچ‌یک از دو روش بالا دسته‌بندی نمی‌شوند. جستجوی درختیِ مونته کاریو یکی از این روش هاست که روی محتمل‌ترین حرکات براساس توسعهٔ درخت جستجو روی نمونه‌سازی تصادفی فضای محل جستجو بنا شده‌است.

درخت دودویی:

اول‌عمق

• دنباله پیمایش پیش‌ترتیب: A, B, D, E, H, I, C, F, G
• دنباله پیمایش میان‌ترتیب: D, B, H, E, I, A, F, C, G
• دنباله پیمایش پس‌ترتیب: D, H, I, E, B, F, G, C, A

اول‌سطح

• دنباله پیمایش سطح‌ترتیب: A, B, C, D, E, F, G, H, I

با اینکه عموماً پیمایش روی درخت‌هایی با تعداد گره محدود انجام می‌شود اما امکان پیاده‌سازی آن روی درخت‌های بی‌نهایت و نامحدود نیز وجود دارد. حتی بعضی درخت‌های محدود نیز آنقدر بزرگند که می‌توان به عنوان درخت‌های بینهایت آن‌ها را مورد بررسی و آنالیز قرار داد مانند درخت بازی یا شطرنج. این یک علاقه خاص در برنامه‌نویسی تابعی است؛ بنابراین ساختمان‌های داده بی‌نهایت اگر (به شدت) مورد ارزیابی قرار نگرفته‌اند اغلب می‌تواند تعریف شود و کار کند، در این صورت زمان بی‌نهایتی خواهد برد. برخی ازدرختان محدود برای نمایش ساده بیش از حد بزرگ هستند نظیر درخت بازی، شطرنج، بازی گو و نظایرآن. این کاری سودمند و مفید است که آن‌ها را به عنوان اینکه اگر آن‌ها بی‌نهایت بودند بررسی کنیم. یک نیاز اساسی برای پیمایش، ملاقات کردن هر گره است. برای درختان بی‌نهایت الگوریتم‌های ساده اغلب به شکست می‌انجامند. به عنوان مثال درخت دودویی داده شده با عمق بی‌نهایت، پیمایش اول-عمق از یک سمت درخت پایین خواهد رفت (بنابر قانون سمت چپ). هیچگاه مابقی را ملاقات نخواهدکرد؛ و در واقع اگر پیمایش میانوندی و پسوندی هیچگاه گرهی را ملاقات نکنند پس باید به برگ رسیده باشند (ولی در واقعیت اینطور نیست). در مقابل، پیمایش اول-سطح (پیمایش سطحی) درخت دودویی با عمق بی‌نهایت را بدون مشکل پیمایش می‌کند؛ و در واقع هر درخت را با فاکتور انشعاب محدود پیمایش می‌کند. به بیانی دیگر درختی با ۲ عمق داده شده که گره ریشه فرزندان بی‌نهایت بسیاری دارد و هر یک از این فرزندان دو فرزند دارند، پیمایش اول-عمق تمامی گره‌ها را ملاقات می‌کند در مرتبه اول از گره‌های نوه (فرزند فرزند هر گره) تهی می‌شود، سپس به سمت بعدی حرکت می‌کند (فرض می‌کنیم که آن پیمایش پسوندی نیست). در مقابل پیمایش اول- سطح هیچگاه به گره نوه نمی‌رسد، بنابراین آن به دنبال تهی کردن فرزند اول است. تجزیه و تحلیل‌های پیچیده تری از زمان اجرا می‌توانند از طریق اعداد ترتیبی نامحدود داده شوند؛ بنابراین جستجوهای اول-عمق یا اول-سطح پیمایشات درخت درخت بی‌نهایت را انجام نمی‌دهند و برای درختان خیلی بزرگ کارآمد نیستند. به هر حال، پیمایشات ترکیبی می‌تواند درختان بی‌نهایت (قابل شمارش) را پیمایش کنند مخصوصاً از طریق اثبات مورب («مورب» ترکیبی است از افقی و عمودی که سطح و عمق را مرتبط می‌کند). مشخصا، شاخه‌های درخت بی‌نهایت داده شده با عمق نامحدود گره ریشه را با علامت ()، فرزندان گره ریشه را با علامت (۱)، (۲) و... نوه‌ها را با علامت (۱٬۱)، (۱٬۲) و ... (۲٬۱)، (۲٬۲)، .... مشخص می‌کند. در نتیجه، گره‌ها در یک تناظر یک به یک با توالی محدودی از اعداد مثبتی هستند، که قابل شمارش اندو می‌توانند برای مرتبه اول به وسیلهٔ مجموع ورودی‌ها و سپس با رعایت ترتیب واژه نگاری بین جمع داده شده (تنها توالی محدود با مقادیر داده شده جمع می‌شوند بنابراین تمامی ورودی‌هایی که به صورت رسمی بدان دسترسی یافته‌است، یک تعداد متناهی از ترکیب یک عدد طبیعی داده شده‌است) که یک پیمایش را می‌دهد، جایگذاری شوند. این می‌تواند به عنوان نگاشت عمق بی‌نهایت درخت باینری بر روی این درخت و سپس پیمایش اول-سطح تفسیر شود: جایگزینی ضلع پایینی متصل به گره والد به فرزندان دوم و بعدی خودش با ضلع سمت راست ازاولین فرزند به دومین فرزند و از دومین فرزند به سومین فرزند و ... . بنابراین در هر مرحله یک یا هر دو می‌توانند به پایین (اضافه کردن یک (۱)) یا به راست (اضافه کردن یک (۱) به آخرین عدد) (بجز ریشه که اضافی است و می‌تواند به پایین برود) بروند، که ارتباط و مراسلات بین درخت دودویی بی‌نهایت وشماره‌گذاری بالا را نشان می‌دهد. مجموع ورودی‌ها (منهای ۱) مربوط به فاصله از ریشه که برابر است با 2n-۱ گره در عمق n-1 در درخت دودویی بی‌نهایت.

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

پیمایش پیشوندی در حالی که گره‌ها و اضلاع را تکثیر می‌کند می‌تواند یک کپی کاملی از درخت دودویی را بسازد. پیمایش میانوندی به شکل رایج تری در جستجوی درخت دودویی مورد استفاده قرار می‌گیرد چراکه مقادیرزیر مجموعه را با توجه به مقایسه‌ای که درخت دودویی پیاده‌سازی می‌کند برمی‌گرداند. پیمایش پسوندی در هنگام حذف یا آزادسازی گره‌ها و مقادیر می‌تواند یک درخت دودویی کامل را حذف کند، همچنین می‌تواند یک پسوند نمایشی از درخت دودویی را ایجاد کند.

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

یک درخت دودویی نخ کشی شده به وسیلهٔ هر اشاره گر فرزند چپ (که در غیر این صورت پوچ است) به پیمایش میانوندی قبلی هر گره (اگر وجود داشته باشد) اشاره می‌کند و هر اشاره گر فرزند راست (که در غیر این صورت پوچ است) به جانشین پیمایش میانوندی هر گره اشاره می‌کند (اگر وجود داشته باشد). مزایا: ۱. چون که از پشته تماس استفاده می‌کند و حافظه و زمان صرف می‌کند از بازگشت اجتناب می‌کند. ۲. گره یک رکورد از والدینش نگه می‌دارد. معایب: ۱. درخت پیچیده‌تر است. ۲. در یک زمان تنها یک پیمایش قابل انجام است. ۳. زمانی که هر دو فرزند حاضر نیستند و هر دو مقادیر گره‌ها به اجدادشان اشاره می‌کنند خیلی مستعد رخ دادن خطاست. پیمایش موریس یک پیاده‌سازی از پیمایش میانوندی است که از نخ کشی استفاده می‌کند: ۱. ایجاد لینک‌هایی به جانشین میانوندی ۲. چاپ داده مورد استفاده این لینک‌ها ۳. برگرداندن تغییرات و بازگرداندن درخت اصلی

• قدسی، محمد. داده‌ساختارها و مبانی الگوریتم‌ها. تهران: مؤسسه فرهنگی فاطمی، ۱۳۸۸ شابک ‎۹۷۸−۹۶۴−۳۱۸−۵۴۹−۷.
• جعفر، تنها. ناصر، آیت. ساختمان داده‌ها و الگوریتم‌ها (رشته کامپیوتر). تهران: دانشگاه پیام‌نور، ۱۳۸۷ شابک ‎۹۷۸−۹۶۴−۳۸۷−۵۰۶−۰.
• Wikipedia contributors, "Tree traversal," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Tree_traversal&oldid=533659477

(accessed 1۸ ژانویه ۲۰۱۳)