Tree data structure in python

● آنچه که در این مقاله به آن می‌پردازیم:

• تفاوت linear data structurs و nonlinear data structures
• معرفی درخت به عنوان یک nonlinear datastructure
• معرفی تعاریف و اصطلاحات مربوط به درخت‌ها
• انواع درخت‌
• پیاده سازی یک درخت در زبان پایتون
• معرفی و پیاده سازی الگوریتم‌های پیمایش درخت
• معرفی نمونه مسائلی که با کمک درخت‌ها حل می‌شوند

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

● تفاوت linear datastrucure و nonlinear data structure

• ساختار داره خطی یا linear:

در این نوع ساختار داده، عناصر به صورت خطی چیده می‌شوند و روابط بین عناصر به صورت after و before تعریف می‌شود. تمام عناطر در یک لول از نظر ساختاری قرار دارند و به همین دلیل میتوان کل ساختار را به یکباره پیمایش کرد. از آنجایی که مموری کامپیوتر‌ها ذاتا به صورت linear چیده شده است، پیاده سازی این نوع ساختار داده راحت است. مثال‌هایی از ساختار داده‌های خطی آرایه ها، صف‌ها، استک و ... است.

• ساختار داده غیرخطی یا nonlinear:

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

● معرفی درخت به عنوان یک ساختار داده غیرخطی:

درخت یک ساختار داده غیرخطی است که در آن عناصر به صورت سلسله مراتبی و با روابط parent-child چیده شده‌اند. هر درخت یک عنصر به عنوان ریشه یا root دارد. معمولا ریشه درخت در پایین آن قرار دارد ولی در علوم کامپیوتر هنگام نمایش درخت ریشه آن را در بالا رسم می‌کنند. برای نمایش درخت عناصر درخت را به صورت دایره و یا شکل‌های دیگر رسم می‌کنند و مقدار عنصر را درون شکل می‌نویسند. با توجه به اینکه در ساختار داده درخت مفهوم سطح (Level) وجود دارد، هر عنصر در سطح مناسب خود قرار می‌گیرد و روابط والد-فرزند ی را با خطوطی که عناصر را به هم وصل می‌کنند مشخص می‌کنیم. برای نمونه تصویر زیر نمونه‌ای از نمایش یک درخت است.

● معرفی تعاریف و اصطلاحات مربوط به درخت‌ها

• نود یا node: به هر عنصر در درخت یک نود یا گره گفته می‌شود. برای مثال هریک از دایره‌های شکل بالا یک نود هستند.
• فرزند یا child: در نمایش درخت‌ها اگر نود a در یک سطح بالاتر از نود b قرار گرفته باشد و با یک خط به b وصل باشد، نود b را فرزند یا child نود a می‌نامیم. مثلا در تصویر بالا نود B فرزند نود A است.
• والد یا parent: در تعریف child، نود a والد یا parent نود b است. مثلا در تصویر بالا نود A والد نود B است.
• شاخه(branch) یا edge: به هرجف نود به شکل (u, v) که در آن u نود والد v باشد یا برعکس، یک edge یا branch گفته می‌شود.
• نود ancestor: نود v را ancestor نود u می‌نامیم اگر u=v یا نود v خود ancestor نود والد u باشد.(لطفا این تعریف را با دقت بیشتری بخوانید!)
• نود descendant: نود u نود descendant نود v است اگر و تنها اگر نود v نود ancestor نود u باشد.
• عمق یا depth: عمق نود p برابر است با تعداد ancestor های نود p به جز خود آن(اگر تعریفی که در بالاتر گفته شد را با دقت خوانده باشید متوجه شدید که هر نود ancestor خودش است). در یک تعریف ساده‌تر، عمق نود p برابر تعداد نودهایی است که از نود p تا خود ریشه قرار گرفته اند.(خود ریشه محاسبه میشود ولی خود p نه). عمق نود root صفر است.
• ارتفاع یا height: ارتفاع نود p برابر با ارتفاع بزرگترین زیردرخت آن است. یعنی تعداد decendant های آن. ارتفاع خود درخت برابر با ارتفاع نود root است.
• خواهر/برادر یا siblings: نود v خواهر/برادر نود u است اگر و تنها اگر parent نود u و v برابر باشد. یعنی هر دو فرزند یک والد باشند.

● انواع درخت‌ها:

درخت‌ها انواع متفاوتی دارند مانند binary tree ها، heap، avl trees، search trees، و ... که ما در این سری مقاله‌ها صرفا General Tree ها و یک نمونه از انواع گفته شده یعنی Binary Tree را بررسی و پیاده سازی می‌کنیم. منظور از General Tree در واقع یک پیاده سازی از درخت است که به عنوان کلاس پایه تمام درخت‌ها می‌تواند استفاده شود و در واقع متدها و ویژگی‌هایی که همه درخت‌ها دارند.

حال که با تعاریف بالا آشنا شدیم، در بخش بعدی یک General Tree Abstract Data Type که در واقع یک کلاس پایه برای تمام انواع درخت‌هااز جمله درختی که ما بعدا پیاده سازی می‌کنیم(binary tree) است، پیاده سازی می‌کنیم. سپس به کمک آن درخت باینری را پیاده سازی میکنیم. دقت کنید که قصد نداریم از هیچ کتابخانه‌ای استفاده کنیم و می‌خواهیم از صفر خودمان یک ساختار داده درخت ایجاد کنیم. برای جلوگیری از طولانی شدن مقاله، ادامه آن را در قسمت بعدی می‌خوانیم.