تماس با ما

هرگونه پیشنهاد و انتقاد خود را با ما در میان بگذارید

پیمایش درختها (درختهای دودویی):

به طور کلی سه روش برای پیمایش یک درخت دودویی وجود دارد:

۱-پیمایش پیش ترتیب(pre order): در این روش اول ریشه دوم زیر درخت چپ و در انتها زیر درخت راست پیمایش میشود به این ترتیب پیمایش پیش ترتیب درخت زیر به صورت ABCDEFGHIJ خواهد شد

۲-پیمایش میان ترتیب (in order):در این روش اول زیر درخت چپ سپس ریشه و در انتها زیر درخت راست پیمایش میشود به این ترتیب پیمایش میان ترتیب درخت زیر به صورت CBDEAFIHJG خواهد شد

۳-پیمایش پس ترتیب (post order):دراین روش ابتدا زیردرخت چپ سپس زیر درخت راست و در انتها ریشه پیمایش میشود به این ترتیب پیمایش پس ترتیب درخت زیر به صورت CEDBIJHGFA خواهد شد

 

 

سوالی که ممکنه پیش بیاد اینه که ممکنه نتیجه پیمایش دو درخت متفاوت یکی بشه؟

درمورد پیمایش preorder شکل زیر دو درخت متفاوت رو نشون میده که پیمایش هردو میشه ABCD

در مورد inorder و postorder هم میشه دو درخت با پیمایش یکسان پیدا کرد کافیه به جای اینکه دنبال دوتا درخت بگردید که پیمایش یکی داشته باشن یه پیمایش از خودتون بنویسید و سعی کنید از روی اون یک درخت دودویی بسازید.

حالا اگر کسی به ما بگه CEDBIJHGFA پیشمایش پس ترتیب یک درخته شما درخت رو رسم کن باید چکار کرد؟ معمولا تو این جور موارد یک راهنمایی هم میکنن مثلا میگن پیمایش پیش ترتیب همون درخت ABCDEFGHIJ است.

حالا ببینیم با داشتن پیمایش پیش ترتیب و پس ترتیب میشه درخت رو بدست آورد؟

اگر کمی دقت کنیم اولین چیزی که متوجه میشیم این است که A ریشه درخت است چون اولین عنصر در پیمایش پیش ترتیبه و همچنین از این پیمایش متوجه میشیم که B باید یکی از فرزندان چپ و یا راست A باشد یعنی یکی از دو درخت زیر:

اما اگر یک نگاه به پیمایش پس ترتیب بکنیم متوجه میشیم که B نمیتونه فرزند راست A باشه چون در این صورت در پیمایش پس ترتیب باید بلافاصله قبل از A ظاهر بشه (همیشه درپیمایش پس ترتیب درخت دودویی آخرین عنصر که قبل از ریشه پیمایش میشود فرزند راست ریشه است به جز زمانی که ریشه فرزند راست نداشته باشه). پس نتیجه میگیریم که B فرزند چپ A است.

نکته:اگر B در پیمایش پیش ترتیب بلافاصله بعد از A قرار بگیره و در پیمایش پس ترتیب بدون فاصله پیش از A باشه در این صورت A فقط یک فرزند داره و فرقی نداره که B فرزند چپ A باشه یا راست, در هر دو حالت پیمایش پیش ترتیب یکی میشه. در مورد پیمایش پس ترتیب هم به همین صورت خواهد بود:

پیمایش پیش ترتیب هر دو درخت میشه:ABCEFD

و پیمایش پس ترتیب هر دو درخت میشه:EFCDBA

این مثال به خوبی نشان میده که حتی با داشتن پیمایش های پیش ترتیب و پس ترتیب نمیشه درخت رو به دست اورد

با توجه به این که در پیمایش پس ترتیب اول فرزندان (اول زیر درخت چپ بعد زیر درخت راست) و سپس ریشه پیمایش میشه و اینکه B فرزند چپ A است و با توجه به اینکه پیمایش پس ترتیب درخت CEDBIJHGFA میشه نتیجه میگیریم که:

۱- C و E و D فرزندان B هستند

۲- F فرزند راست A است

۳- در پیمایش پس ترتیب عناصر بین B و F (یعنی GوHوJوI ) همه در زیر درخت راست قرار دارند و F ریشه ان است

۴- پیمایش پیش ترتیب زیر درخت چپ BCDE و پیمایش پس ترتیب آن CEDB است

۵- پیمایش پیش ترتیب زیر درخت راست FGHIJ و پیمایش پس ترتیب آن IJHGF است

به این ترتیب هر دو پیمایش زیر درخت چپ و راست A به دست میاد و میشه با تکرار همین روش هر دو زیردرخت رو ساخت البته همانطور که گفتم اگر یک گره فقط یک فرزند داشته باشه اونوقت دیگه نمیشه تعیین کرد که فرزند چپ داره یا فرزند راست

نکته: معمولا در تستهای کنکور نیازی نیست که کل درخت ساخته بشه بلکه به محض مشحص شدن زیر درختهای چپ و راست گزینه های غلط مشخص میشه

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

preorder:ABGHCDEKFIJ inorder:GHBACKEDIFG

1-HGBKEIJFDCA

2-BHGIEKJFCDA

3- GHBJFKEIDCA

4-HGBKEIAJFDC

راه حل:با توجه به پیمایش پیش ترتیب متوجه میشیم که ریشه درخت A است پس گزینه ۴ غلطه از طرفی با توجه به پیمایش میان ترتیب متوجه میشیم که G و H و B هر سه باید در زیر درخت چپ A باشند با توجه به پیمایش پیش ترتیب متوجه میشویم که در زیردرخت چپ گره B باید ریشه باشه پس گزینه ۲ هم غلطه حالا یک مسئله کوچکتر داریم که با حل اون مسئله اول حل میشه و اون مسئله اینه:پیمایش پیش ترتیب زیردرخت چپ گره A برابر BGH و پیمایش میان ترتیب آن GHB است درخت کدام است؟

جواب اینه:B ریشه است (با توجه به preorder) و تنها یک فرزند چپ دارد (با توجه به inorder) و اون فرزند G است (با توجه به preorder) و با توجه به اینکه پیمایش میان ترتیب GHB است پس H فرزند راست G است شکل زیر زیر درخت چپ A را نشان میدهد:

واضح است که با توجه به این زیر درخت تنها گزینه ۱ میتونه جواب سوال باشه به این ترتیب بدون بدست اوردن کل درخت مساله حل شد

در شکل زیر درخت مربوط به این تست رسم شده:


لینک های مرتبط:

http://www.hpkclasses.ir/Courses/DataStructure/ds1100.html