(24 دى 1393 04:03 ب.ظ)Ametrine نوشته شده توسط: [ -> ]خب حالا که همه متوجه شدید، یه نفر برا منم توضیح بده :دی
من اصلاً متوجه نمیشم.
کی رفت چپ، کی رفت راست؟!
گره تک فرزندی هم نداره مثالی که تو اون تاپیک هست...
اگه توضیحش مصور باشه بهتره!
اگه امکان داره یه نفر توضیح بده.
من دیشب 2 ساعت رو این مطلب قفل کرده بودم چیزی نغهمیدم
صبح به ذهنم رسید
این دوستمون یجا یه چیزی رو نگفته . من کامل تر میکنم تو پست بعدی و مینویسم کاملشو
(24 دى 1393 04:03 ب.ظ)Ametrine نوشته شده توسط: [ -> ]خب حالا که همه متوجه شدید، یه نفر برا منم توضیح بده :دی
من اصلاً متوجه نمیشم.
کی رفت چپ، کی رفت راست؟!
گره تک فرزندی هم نداره مثالی که تو اون تاپیک هست...
اگه توضیحش مصور باشه بهتره!
اگه امکان داره یه نفر توضیح بده.
شما همون مثال اون تاپیک رو در نظر بگیر
preorder : A,B,D,J,E,O,P,F,C,G,M,H,I,K,L
post : D,O,P,E,F,J,B,G,H,K,L,I,M
خوب شروع کار
بسم الله
اول نیت میکنی واسه حلش ! بعد تمرکز !
حالا بریم
ریشه که سریعا مشخصه A . تا اینجا که مشکلی نباید باشه
تو پیمایش post order آخرین چیزی که پیمایش میشه ریشیت دیگه ؟ ماقبل آخرشم , اولین فرزند راستشه . ( باور نداری امتحان کن )
الان اینجا C تو پیمایش post ماقبل زیشه هست . مشخص میکنه C برای سمت راست هست . حالا میای پیمایش pre رو نگاه میکنی . رو جدا میکنیم . گره های سمت راست C میشن مجموعه گره های سمت چپ A . یعنی B,D,J,E,O,P,F اوکی ؟ و گره های C,G,M,H,I,K,l میشن مجموعه گره های سمت راست A.
خوب حالا تو پیمایش pre نگاه میکنی .
(( تو پیمایش pre چون ما با الگوریتم DFS پیمایش میکنیم . پس بعد از ریشه فرزند سمت چپ پیمایش میشه دیگه . اینجا بعد A فرزند سمت چپش B بوده . درست ؟
حالا توی پیمایش post نگاه میکنی گره های قبل B میشن مجموعه گره های سمت راست ما . یعنی D,O,P,E,F,J,B و بعد از B میشه مجموعه گره های سمت راست A یعنی G,H,K,L,I,M,C درست ؟
حالا بیا کل مجموعه گره های سمت راستت رو یک جا بنویس :
کل مجموعه گره های سمت چپ A:
BDJEOPF: pre
DOPEFJB : post
و کل مجموعه گره های سمت راستش :
pre:C,G,M,H,I,K,L
post: G,H,K,L,I,M,C
حالا یک طرف گره (( یا چپ یا راست )) رو بگیر برو تا ته .
این بخش رو تا اخر میریم اگه نیاز بود سمت راست رو هم بررسی میکنیم
حالا سمت چپ رو بررسی میکنیم :
ار مجموعه گره هاش کاملا مشخصه که B ریشس . همون اولم مشحص کرده بودیم
درست ؟
حالا تو post گره ماقبل ریشه اولین فرزند راست ریشه هستش . تو pre اولین گره بعد از ریشه (( چون جستجو DFS هستش )) فرزند چپ ریشه هستش .
درست ؟
یعنی فرزند سمت چپ B میشه گره D و فرزند سمت راست B میشه گره J
حالا قبل و بعد ریشه ها رو هم عین بالا ادامه میدی و پیدا میکنی
پس برای سمت راست اون میشه
JEOPF: pre
OPEFJ : post
و سمت چپ فقط D میمونه . ( برگ)
حالا باز J میشه ریشه و F ریشه سمت راست و E ریشه سمت چپ میشه که باقی میماند
F فقط سمت راست و سمت چپ داریم
EOP : pre
OPE : post
که E ریشه و سمت چپ O و راست P است پس سمت چپ A میشود
DBOEPJF
الان گزینه ۲و ۴ یکسان هستند باید به این طراح مدال از دست دادن زمان برای داوطلب رو داد Big Grin
میریم که سمت راست رو حل کنیم...
CGMHIKL : pre
GHKLIMC :post
خب ریشه اصلی C , ریشه سمت راست M و ریشه سمت چپ G است سمت چپ فقط یک گره موندG میریم برای سمت راست.
MHIKL : pre
HKLIM : post
ریشه اصلی M , ریشه سمت راست I و ریشه سمت چپ H است سمت چپ فقط یک گره موند H میریم برای سمت راست.
IKL : pre
KLI : post
ریشه = I سمت چپ = k سمت راست=L
خب این سمت هم پیمایش in میشه ....
GCHMKIL
که جواب گزینه ۴ میشه
