سلام

پیمایش inorder این میشه : DBAHGIECF ؟؟؟؟

سلام تنها نکته ای که به ذهن من میرسه اینه که اون جفت گره هایی که تو پیمایشها پشت سر هم هستن ولی جاشون عوض میشه تک فرزندی هستن که تو رسم درخت بهمون کمک میکنه
مثلاBDدرpreorderو DBدرpostorderکه نشون میده Bپدر Dهست و تک فرزندیه.برای جفت گره های EGوGEهم همینطور.
با این نکته حل کنی وقتگیره ولی حل میشه جواب منم شدDBAHGIECF

بله درسته اون میشه جوابش
ولی یه جا یه تست دیدم ۱۲ ۱۳ تا گره داشت
مال سراسری ۹۱
با پیدا کردن گرهای تک فرزندی میشه اینم حل کرد؟

نمیدونم. خیلی سخت میشه و وقت میگیره.
شاید راه حل بهتری باشه براش

(۲۴ دى ۱۳۹۳ ۱۲:۱۶ ب.ظ)m.zeinali نوشته شده توسط:  نمیدونم. خیلی سخت میشه و وقت میگیره.
شاید راه حل بهتری باشه براش

مثلاً این تست :
pre = 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,C,A
inorder = ?
جوابشم میشه
D,B,O,E,P,J,F,A,G,C,H,M,K,I,L
ازکجا ؟
( سراسری ۹۱)

---

(۲۴ دى ۱۳۹۳ ۱۲:۱۹ ب.ظ)Ametrine نوشته شده توسط:  یه نمونه سوال اینجا هم هست:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

مرسی . ولی اصلاً متوجه نمیشم .
خوب قبول C فرزند راست درخت هستش .
تا C گره های سمت چپ و C و بعدش گره های سمت راست . ولی post چطوری شد ؟؟
چرا تو مرحله اول شد : post = d,o,p,e,f,j,b

---

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

خب حالا که همه متوجه شدید، یه نفر برا منم توضیح بده :دی
من اصلاً متوجه نمیشم.
کی رفت چپ، کی رفت راست؟!
گره تک فرزندی هم نداره مثالی که تو اون تاپیک هست...
اگه توضیحش مصور باشه بهتره!
اگه امکان داره یه نفر توضیح بده.

(۲۴ دى ۱۳۹۳ ۰۴:۰۳ ب.ظ)Ametrine نوشته شده توسط:  خب حالا که همه متوجه شدید، یه نفر برا منم توضیح بده :دی
من اصلاً متوجه نمیشم.
کی رفت چپ، کی رفت راست؟!
گره تک فرزندی هم نداره مثالی که تو اون تاپیک هست...
اگه توضیحش مصور باشه بهتره!
اگه امکان داره یه نفر توضیح بده.

من دیشب ۲ ساعت رو این مطلب قفل کرده بودم چیزی نغهمیدم

صبح به ذهنم رسید
این دوستمون یجا یه چیزی رو نگفته . من کامل تر میکنم تو پست بعدی و مینویسم کاملشو

---

(۲۴ دى ۱۳۹۳ ۰۴:۰۳ ب.ظ)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
که جواب گزینه ۴ میشه

ممنون از وقتی که گذاشتید.
واقعا سوال وقت گیری هست و دقت زیادی میخواد.
دقت کردید که سوال اون تاپیک، همین سوال کنکور ۹۱ هست که شما پرسیدید؟ :دی

(۲۴ دى ۱۳۹۳ ۰۸:۲۱ ب.ظ)Ametrine نوشته شده توسط:  ممنون از وقتی که گذاشتید.
واقعا سوال وقت گیری هست و دقت زیادی میخواد.
دقت کردید که سوال اون تاپیک، همین سوال کنکور ۹۱ هست که شما پرسیدید؟ :دی

خواهش میکنم دوست عزیز
همون
:دی
منم تو کتاب محسن طورانی اینو دیدم یه لحظه استرس شدید بهم وارد شد .
با ۲ بار تمرین خیلی آسون میشه دیگه .

یه نمونه سوال اینجا هم هست:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(۲۴ دى ۱۳۹۳ ۱۲:۱۹ ب.ظ)Ametrine نوشته شده توسط:  یه نمونه سوال اینجا هم هست:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

خیلی عالی بود. ممنون...