مبانی و ساختارهای داده در مهندسی کامپیوتر: پیمایش درخت: پس‌نوردی - نکته رسمی

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

1. پیمایش پس نوردی (Postorder Traversal) در درخ تان، روشی است که ابتدا فرزندان چپ و سپس فرزندان راست هر گره پردازش شده و در نهایت خود گره اصلی مورد بازدید قرار می گیرد. این ترتیب پردازش معمولاً برای ارزیابی عبارات ریاضی که با درخت نمایش داده می شوند، مفید است.
2. الگوریتم پیمایش پس نوردی برای یک درخت دودویی به طور بازگشتی به صورت زیر تعریف می شود: ابتدا پیمایش پس نوردی زیردرخت چپ، سپس پیمایش پس نوردی زیردرخت راست، و در نهایت بازدید از گره ریشه.
3. در پیمایش پس نوردی، گره ریشه همیشه آخرین گرهی است که در دنباله پیمایش ظاهر می شود. این ویژگی آن را از پیمایش پیش نوردی (Preorder) و میان نوردی (Inorder) متمایز می سازد.
4. یک کاربرد مهم پیمایش پس نوردی، حذف یک درخت است. با پیمایش گره ها به ترتیب پس نوردی، اطمینان حاصل می شود که هنگام حذف یک گره، تمام زیردرخت های آن قبلاً حذف شده اند و از بروز خطا های دسترسی به حافظه جلوگیری می شود.
5. برای پیاده سازی پیمایش پس نوردی به صورت تکراری (Iterative)، معمولاً از دو پشته (Stack) استفاده می شود. یک پشته برای نگهداری گره های در حال پردازش و پشته دیگر برای نگهداری ترتیب معکوس گره های بازدید شده.
6. درخ تان دودویی جستجو (Binary Search Trees) را می توان با استفاده از پیمایش پس نوردی برای استخراج گره ها در ترتیب مرتب شده، اما با ترتیب معکوس، مورد استفاده قرار داد. این امر به خصوص در الگوریتم های خاصی که نیاز به پردازش گره ها از بزرگ ترین به کوچک ترین دارند، کاربرد دارد.
7. هنگامی که یک عبارت ریاضی به صورت درختی نمایش داده می شود، پیمایش پس نوردی آن، ترتیب عملگر ها و عملوند ها را به گونه ای تولید می کند که بتوان آن را به سادگی به فرم لهستانی معکوس (Reverse Polish Notation - RPN) تبدیل کرد.
8. مثال پیمایش پس نوردی برای درخت زیر: A B C D E دنباله پیمایش پس نوردی: D, E, B, C, A
9. پیچیدگی زمانی پیمایش پس نوردی برای یک درخت با n گره، O(n) است، زیرا هر گره دقیقاً یک بار مورد بازدید قرار می گیرد. پیچیدگی فضایی نیز بسته به روش پیاده سازی (بازگشتی یا تکراری) متفاوت است.
10. تفاوت اصلی پیمایش پس نوردی با پیمایش پیش نوردی در این است که در پیش نوردی، ریشه قبل از فرزندان پردازش می شود، در حالی که در پس نوردی، ریشه پس از تمام فرزندان پردازش می شود.