مرتب‌سازی درختی در سی پلاس پلاس (Tree Sort)

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

پیش‌نیازهای این آموزش در زیر آورده شده است:

  1. درخت دودویی جستجو
  2. توابع در سی پلاس پلاس
  3. Constructor در سی پلاس پلاس
  4. توابع بازگشتی

مرتب‌سازی درختی در سی پلاس پلاس

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

  1. عناصر ورودی را در آرایه وارد کنید.
  2. با وارد کردن داده های آرایه در درخت جستجوی دودویی، یک درخت جستجوی دودویی تشکیل دهید.
  3. بر روی درخت جستجوی دودویی پیمایش میان ترتیب اجرا کنید تا عناصر مرتب شوند.

پیمایش میان ترتیب: در این روش اول زیر درخت چپ سپس ریشه و در انتها زیر درخت راست پیمایش می‌شود به این ترتیب پیمایش میان ترتیب درخت زیر به صورت CBDEAFIHJG خواهد شد.

پیاده‌سازی مرتب‌سازی درختی در سی پلاس پلاس

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

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

توابع و Structهای مورد استفاده در کد بالا به صورت زیر است:

  1. print: تابعی است که پیمایش میان ترتیب را انجام می‌دهد.
  2. insert: این تابع برای وارد کردن عنصری به درخت دودویی ما است.
  3. Node: Struct ای است که عناصر درخت‌ دودویی را در خود نگه‌داری می کند.
  4. Root: ریشه درخت دودویی ما است.
  5. treeSort: مرتب‌سازی درختی ما را با استفاده از توابع بالا پیاده سازی می کند.

ورودی برنامه بالا آرایه‌ای با عناصر 5, 4, 7, 2, 11 می‌باشد و خروجی آن به صورت زیر است:

پسورد: www.codegate.ir

دسته : آموزش ++c, زبان c++

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz