صفحه‌ها: ۱ ۲
سلام
بچه‌ها یه سوال...
اگر preorder & post orderیه درخت دودویی را د اشته باشیم چه طوری می تونیم تعداد گره های تک فرزندی را حساب کنیم؟لطفا جواب بدید.این سوال سال پیش کنکور بوده..
برای مثال این درخت:
preorder: a b d e f g c h i j
post order :d g f e b i j h c a
سلام مریم عزیز
دقت کنی اگر تو پیمایش pre دو تا حرف داشتیم که در پیمایش post برعکس اومده، یک گره تک فرزندی داریم.
الان تو این سوال داریم:
preorder: a b d e f g c h i j
post order
g f e b i j h c aef در پیمایش pre، به صورت fe ظاهر شده پس تا اینجا ۱ گره تک فرزندی داریم. ch هم در pre، به صورت hc در post اومده. پس در کل ۲ تا گره تک فرزندی داریم.
توصیه می کنم ساختمان داده رو جدی بگیری و حتما کتاب تست بگیری براش. مقسمی منبع خوبیه برای تست و پارسه هم برای مفاهیم. موفق باشی
در حقیقت ۳ گره تک فرزندی داریم. e و f و c
راه تشخیص اش اینه که:
- یا درخت رسم کنی (که معقول نیست)
- یا فرمول اش رو حفظ کنی که همونه که ارشد۹۰ گفت
چیزی که مهمه اینه که شما درخت های مختلف رسم کنی و پیمایش های مختلفش رو رسم کنی و مرتبا سعی کنی ازش فرمول استخراج کنی.
روابط بسیار عجیبی در پیمایش های درخت‌ها هست و منحصر به سوال فعلی شما نیست.
ترتیب درج گره‌ها در پیمایش های مختلف متقارن نیست و همین باعث جالب بودنشون هست.
(۲۲ آذر ۱۳۸۹ ۱۲:۱۲ ق.ظ)arshad90 نوشته شده توسط: سلام مریم عزیز
دقت کنی اگر تو پیمایش pre دو تا حرف داشتیم که در پیمایش post برعکس اومده، یک گره تک فرزندی داریم.
الان تو این سوال داریم:
preorder: a b d e f g c h i j
post order
ef در پیمایش pre، به صورت fe ظاهر شده پس تا اینجا ۱ گره تک فرزندی داریم. ch هم در pre، به صورت hc در post اومده. پس در کل ۲ تا گره تک فرزندی داریم.
توصیه می کنم ساختمان داده رو جدی بگیری و حتما کتاب تست بگیری براش. مقسمی منبع خوبیه برای تست و پارسه هم برای مفاهیم. موفق باشی
خیلی عالی بود ارشد ۹۰ عزیز.....
خوشم اومد...مختصر و مفید...
پس با این حساب،باید ۴ گره تک فرزندی داشته باشیم:e,f,c,h
که در کل ۴^۲=۱۶ درخت مختلف با این پیمایش‌ها داریم...درسته؟؟
کتاب تست مقسمی رو دارم.ولی برای حل چنین سوالایی درخت رو می کشه.این نکته رو من توی کتاب ندیدم.(شایدم هنوز به چشمم نخورده)
فکر کنم دوستان همین طوری جواب بدن یک ۲۰ ۳۰ تا ای گره تک فرزندی پیدا بشه.
۳ گره تک فرزندی داره
ef fe
gf fg
ch hc
نشان میدهد که ۳ گره تک فرزندی دارد.
ok.......گرفتم
ولی یه نکته‌ی دیگه مونده.
شماها گفتید اگه تو پیمایش‌ها جای دو تا گره عوض بشه یک گره‌ی تک فرزندی داریم.مثل ef,fe
خوب حالا سوال اینه:کدومشون گره تک فرزندی است؟ f یا e
(۲۳ آذر ۱۳۸۹ ۱۲:۳۶ ق.ظ)Maryam-X نوشته شده توسط: ok.......گرفتم
ولی یه نکته‌ی دیگه مونده.
شماها گفتید اگه تو پیمایش‌ها جای دو تا گره عوض بشه یک گره‌ی تک فرزندی داریم.مثل ef,fe
خوب حالا سوال اینه:کدومشون گره تک فرزندی است؟ f یا e
در پیمایش پیشترتیب (preorder) گره اولی
در پیمایش پسترتیب (Postorder) گره دومی
(۲۲ آذر ۱۳۸۹ ۱۲:۵۱ ق.ظ)bijibuji نوشته شده توسط: - یا درخت رسم کنی (که معقول نیست)
من که کمتر از ۱ دقیقه شکلشو کشیدم.و با توجه به اینکه می دونم توی این حالت جواب رد خور نداره خیلی بهتر از حفظ کردن فرموله.اینم شکلش(که یکی از حالتهای شکلش می باشد با توجه به اینکه تک فرزندی‌ها رو می تونید چپ یا راست والدشون بدید شکلهای متفاوتی ایجاد میشه):
[attachment=7415]
خیلی راحت طراح می تونه سوال رو طوری عوض کنه که اون فرمول اصلا بدردتون نخوره!
(۲۳ آذر ۱۳۸۹ ۰۸:۲۰ ب.ظ)حامد نوشته شده توسط:ممنون به نظر هم گاهی وقتها راه طولانی‌تر بهتره.اما در کل بهتره که هم درخت بکشید هم از فرمول استفاده کنید که خیالتون تخت بشه!(22 آذر ۱۳۸۹ ۱۲:۵۱ ق.ظ)bijibuji نوشته شده توسط: - یا درخت رسم کنی (که معقول نیست)
من که کمتر از ۱ دقیقه شکلشو کشیدم.و با توجه به اینکه می دونم توی این حالت جواب رد خور نداره خیلی بهتر از حفظ کردن فرموله.اینم شکلش(که یکی از حالتهای شکلش می باشد با توجه به اینکه تک فرزندی‌ها رو می تونید چپ یا راست والدشون بدید شکلهای متفاوتی ایجاد میشه):
خیلی راحت طراح می تونه سوال رو طوری عوض کنه که اون فرمول اصلا بدردتون نخوره!
شما در کمتر از یک دقیقه در شرایطی این درخت رو رسم کردید که ناهار خورده بودید و داشتید در کنار چک کردن ایمیل تون به این سوالات هم پاسخ می دادید.
شرایط سر جلسه ممکنه به بعضی‌ها اجازه این همه ریلکس بودن رو نده. دوبار هی درخت رو می کشی و هی توی بلندگو داد می زنن که مراقبین به ضابطین در باره معاونین و سالکین کمک کنن. اجرای ماده ده بند ۷ ...
و هی تکرارش می کنه
در حالی که ۲۰۰ سوال دیگه منتظر شماست.
منظورم من از معقول نبودن این بود که رسم درخت ابتدایی ترین راه حله. نگفتم راه بدیه. فقط راه بسیار ابتدایی یی هست.
طراحان سوال، کنکور رو طوری تنظیم می کنن که همه سوالات رو نشه از راه های ابتدایی شون حل کرد. وقت محدوده، تنوع درس‌ها و سوالات زیاد و امکان تمکرز پایین
در همچین شرایطی حفظ فرمول می تونه کمک کنه.
باز هم هر کس هر طور که راحته عمل کنه .
امیدوارم که همه موفق باشیم.
(۲۴ آذر ۱۳۸۹ ۰۳:۰۴ ق.ظ)bijibuji نوشته شده توسط: شما در کمتر از یک دقیقه در شرایطی این درخت رو رسم کردید که ناهار خورده بودید و داشتید در کنار چک کردن ایمیل تون به این سوالات هم پاسخ می دادید.من می خواستم بگم اگر سوال مثلا بود که چند جفت برگ در یک سطح قرار ندارند؟ یا اینکه کدام یک از برگ‌ها می تواند فرزند چپ فلان برگ قرار بگیرند؟ یا اختلاف سطح کدام جفت گره تک فرزندی ماکزیمم است؟ یا اصلا یه رابطه‌ی کاملا جدید رو تعریف کنه و بخواد شما توی این درخت پیاده سازی کنید.در اون صورت جواب دادن با استفاده از راه حل غیر شکل سر جلسه تمرکز به مراتب بیشتری می خواد.
شرایط سر جلسه ممکنه به بعضی‌ها اجازه این همه ریلکس بودن رو نده. دوبار هی درخت رو می کشی و هی توی بلندگو داد می زنن که مراقبین به ضابطین در باره معاونین و سالکین کمک کنن. اجرای ماده ده بند ۷ ...
و هی تکرارش می کنه
در حالی که ۲۰۰ سوال دیگه منتظر شماست.
منظورم من از معقول نبودن این بود که رسم درخت ابتدایی ترین راه حله. نگفتم راه بدیه. فقط راه بسیار ابتدایی یی هست.
طراحان سوال، کنکور رو طوری تنظیم می کنن که همه سوالات رو نشه از راه های ابتدایی شون حل کرد. وقت محدوده، تنوع درس‌ها و سوالات زیاد و امکان تمکرز پایین
در همچین شرایطی حفظ فرمول می تونه کمک کنه.
باز هم هر کس هر طور که راحته عمل کنه .
امیدوارم که همه موفق باشیم.
درسته
مسائل محتلف راه حل هاشون مختلفه
با یک فرمول فقط یک نوع مساله رو می شه حل کرد
سلام
بروبچ یه سوال دیگه در باره‌ی این پیمایش ها:
اگر دو تا راس در پیمایش پیش ترتیب و پس ترتیب دقیقا به یک ترتیب بیایند اونوقت این معنیش چیه؟
مثل این:
g e j c b f i d a h
h f g b c e j a d i
e & j به یک ترتیب اومدند.
۲-الان اینجا چند تا گره‌ی تک فرزندی داریم؟
(۱۸ دى ۱۳۸۹ ۱۲:۱۷ ق.ظ)Maryam-X نوشته شده توسط: سلام
بروبچ یه سوال دیگه در باره‌ی این پیمایش ها:
اگر دو تا راس در پیمایش پیش ترتیب و پس ترتیب دقیقا به یک ترتیب بیایند اونوقت این معنیش چیه؟
مثل این:
g e j c b f i d a h
h f g b c e j a d i
e & j به یک ترتیب اومدند.
۲-الان اینجا چند تا گره‌ی تک فرزندی داریم؟
درخت رو که بکشید می توان به این نتیجه رسید که: هر وقت که دو برگ همزاد باشند( داری والد یکسان باشند) در پیمایش پیش ترتیب و پس ترتیب دقیقا به یک ترتیب می آیند.
۳ تا گره‌ی تک فرزندی دارید که با توجه به شکل b ,a و d می باشند.از اون فرمول که بروبچ گفتند هم می تونید استفاده کنید.cb=>bc.id=>di.da=>ad.
سلام بچه‌ها یه سوال دارم
یک الگوریتم بازگشتی برای حذف کلیدگره های یکدرخت دودیی بنویسید(به چنین توابعی مخرب میگویند)
mer30