پیمایش درخت
میخواهیم با حرکت روی یالهای یک درخت، همهٔ گرههای آن را هر کدام یک بار ملاقات کنیم. به این کار پیمایش درخت میگویند. بسته به این که کدام عنصر، کی ملاقات شود، پیمایش درخت لیست یا یک ترتیب خطی از عناصر آن درخت به ما میدهد. طبیعتاً پیمایشهای متفاوت ترتیبهای متفاوتی خواهند داد. سه روش معمول پیمایش درخت که بیشتر برای پیمایش درخت دودویی به کار میروند، عبارتند از:
محتویات |
اولعمق [ویرایش]
- همچنین ببینید: الگوریتم جستجوی عمق اول
سه نوع پیمایش عمق اول وجود دارد: پیش ترتیب، میان تربیب و پس تربیب.
پیمایش پیشترتیب:
- ریشه را ملاقات کن.
- زیر درخت چپ را پیمایش کن.
- زیر درخت راست را پیمایش کن.
پیمایش میانترتیب:
- زیردرخت چپ را پیمایش کن.
- ریشه را ملاقات کن.
- زیردرخت راست را پیمایش کن.
پیمایش پسترتیب:
- زیر درخت چپ را پیمایش کن.
- زیر درخت راست را پیمایش کن.
- ریشه را ملاقات کن.
هر کدام از این روشهای پیمایش را میتوان به دو روش بازگشتی و غیر بازگشتی پیادهسازی کرد.
اولسطح [ویرایش]
- همچنین ببینید: الگوریتم جستجوی اول سطح
درخت ها می توانند به صورت سطح تربیب پیمایش شوند، به طوریکه همه گره ها در یک سطح را ملاقات می کنیم، سپس به ترتیب به سطوح پایین تر می رویم و تمام گره های آنها را ملاقات می کنیم.
مثال [ویرایش]
- اولعمق
- دنباله پیمایش پیشترتیب: A, B, D, E, H, I, C, F, G
- دنباله پیمایش میانترتیب: D, B, H, E, I, A, F, C, G
- دنباله پیمایش پسترتیب: D, H, I, E, B, F, G, C, A
- اولسطح
- دنباله پیمایش سطحتربیب: A, B, C, D, E, F, G, H, I
منابع [ویرایش]
- قدسی، محمد. دادهساختارها و مبانی الگوریتمها. تهران : موسسه فرهنگی فاطمی ، ۱۳۸۸ ISBN ۹۷۸-۹۶۴-۳۱۸-۵۴۹-۷.
- جعفر، تنها. ناصر، آیت. ساختمان دادهها و الگوریتمها(رشته کامپیوتر). تهران : دانشگاه پیامنور ، ۱۳۸۷ ISBN ۹۷۸-۹۶۴-۳۸۷-۵۰۶-۰.
- Wikipedia contributors, "Tree traversal," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Tree_traversal&oldid=533659477
(accessed 18 January 2013)
