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