درخت در ساختمان داده‌ها چیست و چگونه پیمایش می‌شود؟

درخت در ساختمان داده‌ها چیست؟

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

          o

        / | \

       o  o  o

      / \    |

     o   o   o

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

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

مطلب پیشنهادی

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

آشنایی با انواع درخت‌ها در ساختمان داده‌ها

پیمایش درخت

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

درخت در بسیاری از نرم‌افزارهای کامپیوتری، به عنوان یک ساختار داده‌ای پر استفاده است. برای مثال، درخت‌ها در الگوریتم‌های جستجوی باینری و پیدا کردن راه حل‌های بهینه در مسائل بهینه‌سازی استفاده می‌شوند. همچنین، پیمایش درخت در نرم‌افزارهای گرافیکی و بازی‌سازی، به منظور رسم و نمایش اشیاء گرافیکی، نیز کاربرد دارد.

پیمایش درخت چه انواعی دارد؟

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

پیمایش درخت به‌شکل عمقی (Depth-First Search)

• پیمایش درخت به شکل عمقی DFS سرنام Depth-First Search  یکی از روش‌های پیمایش درخت است که در آن ابتدا یک راس به عنوان راس شروع انتخاب می‌شود و سپس برای هر یال، تمام فرزندان یک راس به ترتیب بازدید می‌شوند. به عبارت دیگر، در این روش، ابتدا به یک راس می‌رویم و سپس به تمام فرزندان آن راس باز می‌گردیم و به همین ترتیب ادامه می‌دهیم تا به دنباله‌ای از راس‌ها برسیم.
• پیمایش درخت به شکل عمقی به دو نوع بازگشتی (recursive) و پشته‌ای (stack-based) تقسیم می‌شود. در روش بازگشتی، پیمایش با استفاده از تابع بازگشتی اجرا می‌شود و در هر مرحله، فرزندان راس فعلی به ترتیب بازدید می‌شوند. در روش پشته‌ای، از یک پشته برای ذخیره رئوس استفاده می‌شود و در هر مرحله راس فعلی روی پشته قرار می‌گیرد و سپس تمام فرزندان آن به ترتیب به پشته اضافه می‌شوند.

با توجه به ساختار درخت، پیمایش به شکل عمقی ممکن است به‌صورت پیمایش بهترین اولین (Depth-First Search with Best-First) نیز انجام شود. در این روش، قبل از بازدید از هر راس، تابعی برای ارزیابی کیفیت آن تعریف می‌شود و در هر مرحله، راس با بهترین ارزیابی به عنوان راس بعدی انتخاب می‌شود.

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

مطلب پیشنهادی

آشنایی با مهم‌ترین الگوهای زیرساختی

چرا یادگیری ساختمان داده‌ها برای هر برنامه‌نویسی ضروری است؟

پیمایش درخت به‌صورت سطحی (Breadth-First Search)

پیمایش درخت به صورت سطحی BFS  سرنام Breadth-First Search یکی از روش‌های پیمایش درخت است که در آن در ابتدا ریشه را انتخاب کرده و سپس به ترتیب اولین فرزندان همه رئوس در سطح کنونی را بازدید می‌کنیم و سپس به سطح بعدی می‌رویم. به عبارت دیگر، در این روش، ابتدا به تمام فرزندان راس شروع بازدید می‌کنیم و سپس به تمام فرزندان آن‌ها و به همین ترتیب ادامه می‌دهیم.

پیمایش درخت به صورت سطحی به دو نوع صف (queue-based) و دوطرفه (double-ended queue) تقسیم می‌شود. در روش صف، از یک صف برای ذخیره رئوس استفاده می‌شود و در هر مرحله راس فعلی از صف خارج شده و تمام فرزندان آن به صف اضافه می‌شوند. در روش دوطرفه، از یک صف دوطرفه برای ذخیره رئوس استفاده می‌شود و در هر مرحله، رئوس در دو سمت صف به ترتیب بازدید می‌شوند.

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

پیمایش پس‌ترتیب (Post-order Traversal)

پیمایش پست‌ترتیب یا Post-order Traversal یکی از روش‌های پیمایش درخت است که در آن پیمایش ابتدا از فرزندان یک راس شروع می‌شود، سپس به راس فعلی باز می‌گردیم و سپس به راس پدر و سپس به راس دیگری در چپ یا راست پدر می‌رویم. به عبارت دیگر، در این روش، ابتدا به تمام فرزندان یک راس بازدید می‌شود و سپس خود راس.

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

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

پیمایش پیش‌ترتیب (Pre-order Traversal)

پیمایش پیش‌ترتیب یا Pre-order Traversal یکی از روش‌های پیمایش درخت است که در آن پیمایش از ریشه شروع می‌شود و سپس به ترتیب چپ و راست یک راس بازدید می‌شود. به عبارت دیگر، در این روش، ابتدا راس فعلی را بازدید می‌کنیم و سپس به تمام فرزندان چپ و سپس به تمام فرزندان راست آن‌ها بازدید می‌کنیم.

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

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

پیمایش میان‌ترتیب (In-order Traversal)

پیمایش میان‌ترتیب یا In-order Traversal یکی از روش‌های پیمایش درخت است که در آن پیمایش به ترتیب فرزندان چپ، راس فعلی و سپس فرزندان راست یک راس بازدید می‌شود. به عبارت دیگر، در این روش، ابتدا به تمام فرزندان چپ راس فعلی بازدید می‌کنیم، سپس خود راس و سپس به تمام فرزندان راست آن بازدید می‌کنیم.

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

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

چه الگوریتم‌های دیگری از پیمایش درخت وجود دارد؟

علاوه بر پیمایش پیش‌ترتیب، پیمایش میان‌ترتیب و پیمایش پس‌ترتیب، الگوریتم‌های دیگری برای پیمایش درخت وجود دارند که به طور کلی به دو دسته پیمایش‌های اول سطح (Breadth-First Traversal) و پیمایش‌های اول عمق (Depth-First Traversal) تقسیم می‌شوند. در زیر برخی از این الگوریتم‌ها ذکر شده‌اند:

1. پیمایش سطح (Level-Order Traversal): در این الگوریتم ابتدا از ریشه شروع می‌شود و راس‌های هر سطح به ترتیب پیمایش می‌شوند، سپس به سطح بعدی پرداخته می‌شود.
2. پیمایش اول عمق (Depth-First Search - DFS): در این الگوریتم از ریشه شروع می‌شود و به ترتیب تمام فرزندان یک راس پیمایش می‌شوند، سپس به راس بعدی پرداخته می‌شود، تا زمانی که تمام راس‌ها پیمایش شوند.
3. پیمایش عمق اول چپ (Depth-First Traversal - Left First): این الگوریتم شبیه به الگوریتم DFS است، با این تفاوت که در هر مرحله اولین فرزند چپ یک راس پیمایش می‌شود.
4. پیمایش عمق اول راست (Depth-First Traversal - Right First): این الگوریتم نیز شبیه به الگوریتم DFS است، با این تفاوت که در هر مرحله اولین فرزند راست یک راس پیمایش می‌شود.
5. پیمایش پیش‌ترتیب دوگانه (Double Pre-order Traversal): در این الگوریتم، به ترتیب فرزندان چپ یک راس پیمایش می‌شود، سپس به خود راس، سپس به تمام فرزندان راست آن‌ها پیمایش می‌شود.
6. پیمایش میان‌ترتیب دوگانه (Double In-order Traversal): در این الگوریتم، به ترتیب فرزندان راست یک راس پیمایش می‌شود، سپس خود راس، سپس به تمام فرزندان چپ آن‌ها پیمایش می‌شود.
7. پیمایش پس‌ترتیب دوگانه (Double Post-order Traversal): در این الگوریتم، به ترتیب فرزندان راست یک راس پیمایش می‌شود، سپس به تمام فرزندان چپ آن‌ها پیمایش می‌شود و در نهایت به خود راس بازدید می‌شود.

تکنیک‌های دیگری همچون پیمایش پیش‌ترتیب غیربازگشتی و پیمایش میان‌ترتیب غیربازگشتی نیز وجود دارند که برای پیمایش درخت با استفاده از پشته صورت می‌گیرند. در این روش‌ها، به جای استفاده از بازگشت‌های بازگشتی، از یک پشته برای ذخیره رئوس استفاده می‌شود. با این روش، از تمام مزایای الگوریتم‌های DFS بهره‌مند هستیم، اما نیازی به استفاده از حافظه با طول بردار یا صف نیست.

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

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

درخت عمومی یک نوع درخت است که در آن هر راس می‌تواند بیش از یک فرزند داشته باشد. در واقع، درخت عمومی مانند یک شبکه از رئوس است که هر راس غیر از ریشه می‌تواند چندین فرزند داشته باشد.

در درخت عمومی، هر راس شامل دو بخش است: داده و یک لیست از فرزندانش. برای مثال، می‌توانید یک درخت عمومی از شخصیت‌های یک کتاب بسازید، به طوری که هر شخصیت یک راس است و فرزندان آن شامل شخصیت‌هایی هستند که او را دنبال می‌کنند.

درخت عمومی در بسیاری از الگوریتم‌های پردازش درختی، مانند الگوریتم پیمایش درخت و الگوریتم محاسبه ارتفاع یک درخت، استفاده می‌شود. همچنین، درخت عمومی می‌تواند برای نشان دادن ساختار داده‌هایی مانند XML و HTML نیز استفاده شود.

درخت‌ بینهایت چیست؟

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

          o

          |

          o

          |

          o

          |

          o

         ...

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

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

کلام آخر

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