آموزش پیمایش درخت در ساختمان داده | جامع همراه با مثال

مقدمه آموزش پیمایش درخت در ساختمان داده

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

پیمایش درخت در ساختمان داده یکی از مباحث اصلی درس ساختمان داده می‌باشد که انواع مختلفی دارد و در ادامه به توضیح هر‌ کدام از آن‌ها خواهیم پرداخت. با ادامه آموزش با ما همراه باشید.

درخت چیست؟

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

1. دارای یک گره خاص و مرکزی به نام ریشه است.
2. بقیه گره‌ها هم هر یک به‌نوبه خود درخت هستند و به N ≥ ۰ مجموعه مجزا T1 … Tn تقسیم می‌شوند.
3. در درخت حلقه نداریم و هیچ‌کدام از زیر درخت‌ها مستقیم به هم متصل نیستند.

شکل زیر نمونه‌ای از یک درخت را نشان می‌دهد:

در ادامه به پیمایش درخت در ساختمان داده خواهیم پرداخت.

پیمایش درخت در ساختمان داده

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

اگر L را حرکت به چپ، R را حرکت به راست، V را رسیدن به گره در نظر بگیریم، برای پیمایش یک درخت شش ترکیب ممکن زیر وجود خواهند داشت: RLV, RVL, VRL, VLR, LRV, LVR . اما اگر تنها حالتی را در نظر بگیریم که ابتدا به سمت چپ و بعد به راست حرکت کنیم در این صورت فقط سه ترکیب وجود خواهد داشت: VLR, LRV, LVR .

این سه حالت را به ترتیب Preorder, Inorder, Postorder می‌نامند، این نام‌گذاری به جهت نحوه‌ی قرار گرفتن موقعیت V نسبت به L و R است. مثلا در Postorder, ابتدا زیردرخت‌ها پیمایش می‌شوند و بعد نوبت به گره می‌رسد درحالی‌که در Preorder, اول گره را ملاقات می‌کنیم بعد به پیمایش زیر‌ درخت‌ها می‌پردازیم. پس سه نوع پیمایش درخت داریم:

1. پیمایش پس ترتیب Postorder
2. پیمایش میان ترتیب Inorder
3. پیمایش پیش ترتیب Preorder

پاورپوینت پیمایش درخت در ساختمان داده

کلیک کنید

پیمایش Inorder (LNR)

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

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

مثال ۱ از پیمایش میان ترتیب Inorder

می‌خواهیم پیمایش Inorder درخت زیر را به دست آوریم:

ابتدا زیر درخت سمت چپ A را پیمایش می‌کنیم که یک درخت به شمار می‌رود. در این زیر درخت هم اول به سراغ زیر درخت سمت چپ که ریشه آن D است می‌رویم. در این زیر درخت به سراغ گره سمت چپ یعنی H رفته بعد به سراغ ریشه آن یعنی D رفته و بعد گره سمت راست یعنی I رفته و بعد از پیمایش آن‌ها به سمت بالا برمی‌گردیم. گره B و بعد فرزند راست یعنی E را پیمایش می‌کنیم و مجددا به بالا برمی‌گردیم و گره A را پیمایش می‌کنیم.

در این زمینه فایل آماده‌ای در قالب سورس کد موجود است و برای کسب اطلاعات بیشتر بهتر است مد نظر قرار دهید.

• پیمایش درخت Inorder در سی پلاس پلاس ++ C — کلیک کنید.

حالا به سمت راست درخت می‌رویم، ابتدا به سراغ زیر درخت سمت چپ با‌ریشه F رفته و چون گره سمت چپ ندارد، اول ریشه F پیمایش شده و بعد گره سمت راست یعنی J را پیمایش می‌کنیم. سپس به ریشه C برگشته و بعد از پیمایش آن به گره سمت راست آن یعنی G رفته و پیمایش را به‌پایان می‌رسانیم. در پیمایش LNR, آخرین گره سمت چپ در اول و آخرین گره سمت راست در آخر قرار می‌گیرند. ترتیب پیمایش گره‌ها به صورت زیر است:

H D I B E A F J C G

مثال ۲ از پیمایش میان ترتیب Inorder

می‌خواهیم با یک مثال دیگر پیمایش Inorder، که یکی از روش‌های پیمایش درخت در ساختمان داده است را در درخت زیر را به دست آوریم:

در این مثال هم ابتدا زیر درخت سمت چپ ریشه A را بررسی می‌کنیم. اول سراغ پایین‌ترین زیر درخت سمت چپ می‌رویم که گره N است بعد از پیمایش آن گره ریشه F و بعد هم M را پیمایش کرده و به‌عقب برمی‌گردیم. حالا نوبت ریشه D و بعد از آن هم نوبت زیر درخت سمت راس آن یعنی H است. سپس به گره ریشه B می‌رسیم و بعد از پیمایش خود گره B به زیر درخت سمت راست آن می‌رویم. در آنجا هم به ترتیب اول I بعد ریشه E و سپس L را پیمایش می‌کنیم.

حالا نوبت به زیر درخت سمت راست ریشه A می‌رسد که در آن‌جا هم به ترتیب اول G و بعد C پیمایش می‌شوند و کار خاتمه می‌یابد. ترتیب پیمایش گره‌ها به صورت زیر است:

N F M D H B I E L A C G

پیمایش Preorder (NLR)

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

مثال ۱ از پیمایش پیش ترتیب Preorder

می‌خواهیم پیمایش Preorder درخت زیر را به دست آوریم:

اول ریشه A را پیمایش می‌کنیم بعد به سراغ زیر درخت B رفته و بعد از پیمایش خود ریشه B به زیر درخت چپ یعنی D می‌رویم . بعد از پیمایش خود D زیر درخت سمت چپ آن یعنی H و بعد زیر درخت سمت راست یعنی I را پیمایش کرده و به ریشه D برگشته و از آن به ریشه B رفته و گره E را پیمایش می‌کنیم.

حالا نوبت سمت راست ریشه A است که پیمایش شود. برای این کار ابتدا ریشه زیر درخت سمت راست یعنی C پیمایش شده بعد به زیر درخت سمت چپ رفته و گره F را پیمایش می‌نماییم. چون گره ریشه F زیر درخت چپ ندارد به سراغ زیر درخت راست یعنی J رفته و آن را پیمایش می‌کنیم، سپس به ریشه F بازگشته و از آن به ریشه C رسیده و زیر درخت سمت راست آن یعنی G را پیمایش می‌کنیم و کار پایان می‌یابد. در پیمایش NLR ریشه درخت در ابتدا و آخرین گره در سمت راست در آخر ظاهر می‌شود، ترتیب پیمایش گره‌ها به‌صورت زیر است:

A B D H I E C F J 

پیمایش درخت preorder در سی پلاس پلاس ++C

کلیک کنید

مثال ۲ از پیمایش پیش ترتیب Preorder

می‌خواهیم با یک مثال دیگر پیمایش Preorder، که از روش‌های پیمایش درخت در ساختمان داده است را در درخت زیر به دست آوریم:

در این مثال اول ریشه A را پیمایش کرده و بعد به سراغ زیر درخت سمت چپ رفته و ریشه B را پیمایش می‌کنیم، بعد باز به زیر درخت چپ آن رفته و ریشه D و بعد هم ریشه F را پیمایش می‌کنیم. سپس گره N و بعد هم گره M را پیمایش کرده و برمی‌گردیم. حالا نوبت گره H است و بعد به عقب بازگشته و به زیر درخت سمت راست گره B می‌رویم . ابتدا گره E و بعد به ترتیب گره‌های I و L را پیمایش کرده و به عقب بازمی‌گردیم.

این بار نوبت زیر درخت سمت راست ریشه A است که به ترتیب اول C و بعد G پیمایش شده و کار خاتمه می‌یابد. ترتیب پیمایش گره‌ها به‌صورت زیر است:

A B D F N M H E I L C G

پیمایش درخت preorder در سی پلاس پلاس ++C

کلیک کنید

پیمایش Postorder (LRN)

سومین نوع پیمایش درخت در ساختمان داده، پیمایش Postorder است. در این پیمایش ابتدا زیر درخت چپ بعد زیر درخت راست و در آخر ریشه پیمایش می‌شوند.

مثال ۱ از پیمایش پس ترتیب Postorder

می‌خواهیم پیمایش Postorder درخت زیر را به دست آوریم:ابتدا از پایین‌ترین زیر درخت سمت چپ شروع می‌کنیم یعنی گره H، بعد سراغ گره I می‌رویم و بعد از پیمایش آن ریشه D را پیمایش می‌کنیم. سپس نوبت گره E و بعد از آن هم نوبت ریشه B است. حالا به زیر درخت سمت راست ریشه A می‌رویم و از پایین‌ترین زیر درخت سمت چپ شروع به پیمایش می‌کنیم. چون در سمت چپ زیر درختی وجود ندارد از سمت راست J راپیمایش کرده و بعد سراغ F رفته و آن را پیمایش می‌کنیم.

در مرحله بعد G و پس از آن هم نوبت به C می‌رسد. در آخر هم گره A، یعنی ریشه اصلی را پیمایش کرده و کار خاتمه می‌یابد. ترتیب پیمایش گره‌ها به صورت زیر است:

H I D E B J F G C A

مثال ۲ از پیمایش پس ترتیب Postorder

می‌خواهیم با یک مثال دیگر پیمایش Postorder، که نوع سوم از روش‌های پیمایش درخت در ساختمان داده است را در درخت زیر به دست آوریم:

در این مثال هم ابتدا به پایین‌ترین زیر درخت سمت چپ رفته و از پایین‌ترین گره سمت چپ شروع به پیمایش می‌کنیم. اول گره N بعد گره M و بعد نوبت به ریشه F می‌رسد، حالا به عقب برگشته و گره H را پیمایش کرده و بعد گره ریشه D را پیمایش می‌کنیم. این بار نوبت زیر درخت سمت راست ریشه B است، به پایین‌ترین گره سمت چپ یعنی I رفته و بعد از پیمایش آن به سراغ گره L و بعد هم ریشه E رفته و آن‌ها را پیمایش کرده و در نهایت ریشه B را پیمایش می‌کنیم.

حالا به زیر درخت سمت راست ریشه A رفته و از گره G شروع می‌کنیم، بعد از آن هم گره C و در آخر هم گره ریشه اصلی A پیمایش شده و کار خاتمه می‌یابد. ترتیب پیمایش گره‌ها به صورت زیر است:

N M F H D I L E B G C A

سخن پایانی درباره آموزش پیمایش درخت در ساختمان داده

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

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