Tree Abstract Base Class

در قسمت قبلی این مقاله راجع به مقدمات ساختار داده غیرخطی و یک نوع آن یعنی درخت‌ها صحبت کردیم و تا حدودی با آن آشنایی پیدا کردیم. همانطور که گفته شد قصد داریم از صفر یک پیاده سازی از یکی از انواع معروف درخت‌ها یعنی Binary Trees انجام بدهیم. در این قسمت می‌خواهیم یک کلاس را Implement کنیم که بتوان از آن به عنوان کلاس پایه تمام انواع درخت‌ها از جمله درخت مورد مطالعه ما استفاده کرد. در قسمت قبلی از این کلاس به عنوان General Tree یاد کردیم. ما برای سادگی از abstract base class پایتون استفاده نمی‌کنیم و صرفا یک ارور NotImplementedError را rasie می‌کنیم. هر نود را به صورت یک Position در نظر می‌گیریم که در واقع یک عضو از base class ما است و خود یک کلاس است. متد سازنده کلاس Position دو آرگومانِ container و node را به عنوان ورودی گرفته و همچین متدهای __eq__ و __ne__ را هم implement می‌کند. دلیل استفاده از container به عنوان یک اتریبیوت این است که کاربر نتواند نودی که متعلق به این درخت نیست را به آن الحاق کند و باعث بروز مشکلات بعدی شود(در ادامه واضح تر میبینیم). متدهایی که میخواهیم پیاده سازی کنیم در کلاس پایه، به صورت زیر هستند:

• root()
• is_root(p)
• is_leaf(p)
• parent(p)
• children(p)
• pisitions()
• num_children(p)
• __iter__()
• __len__()
• is_empty()

متد root نود روت را برمیگرداند. متد در صورتی که پوزیشنی که به عنوان آرگومان می‌گیرد نود روت باشد True و در غیر این صورت False را برگشت می‌دهد. بقیه متدها هم در واقع نام گذاری متد مشخص کننده کاری است که انجام می‌دهد و فکر نمی‌کنم نیاز به توضیح اضافه باشد. مثلا متد num_children یک پوزیشن p را به عنوان آرگومان گرفته و تعداد نود‌های فرزند آن را بر‌میگرداند. همچنین متد positions تمام پوزیشن‌های درخت را بر‌میگرداند.

کلاس Position صرفا متد زیر را ساپورت می‌کند.

• element()

و البته داندر‌های __eq__ و __ne__ را هم برای راحتی استفاده پیاده سازی میکنیم.(مورد استفاده اینها را بعدا هنگام validate کردن پوزیشن‌ها خواهیم دید)

کلاس Tree متدهای پیمایش درخت و همچین height و depth را هم پیاده سازی می‌کند اما در اینجا از پیاده‌سازی آن‌ها صرف نظر کرده تا هنگامی که به مباحث مربوط به الگوریتم‌های پیمایش درخت رسیدیم در آن‌جا آن‌ها را پیاده می‌کنیم.

● پیاده سازی General Tree Abstract Data Type در قالب کلاس Tree

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

خب تا این لحظه ما توانستیم یک absrtact base class برای تمام انواع ساختار داده درخت در پایتون پیاده کنیم. در مرحله بعد ما سعی می‌کنیم درخت مورد مطالعه خود یعنی Binary Tree را پیاده کنیم. ادامه مقاله را در قسمت بعد خواهیم خواند.