کدام یک از دنباله های زیر می تواند پیمایش پیش ترتیب یک درخت دودویی جست و جوی با ۱۲ گره باشد؟
۱)(۱۲،۸،۵،۱۰،۹،۲۰،۱۴،۱۵،۱۸،۱۳،۱۶،۱۹)
۲)(۱۴،۱۳،۱۸،۱۵،۱۶،۱۹، ۱۲،۸،۵،۱۰،۹،۲۰)
۳)(۲۰،۱۴،۱۳،۱۲،۸،۵،۹،۱۸،۱۰،۱۹،۱۵،۱۶)
۴)(۲۰،۱۴،۱۳،۱۲،۸،۵،۹،۱۰،۱۸،۱۹،۱۵،۱۶)
دوستان خوب ما برای همه گزینه ها شکل پیش ترتیب درختو رسم کنیم درخت دودویی حفظ میشه پس اشکال کار من کجاست؟؟ .یعنی طبق قضیه که ریشه باید بزرگتر از زیرشاخه سمت چپ و کوچیکتر از زیرشاخه راست باشه شکلو رسم میکنیم اگر درخت دودویی بود جواب ما همون گزینه میشه.
خوب در این سوال میشه گزینه هارو برام رد کنید. من متوجه بشم
جواب گزینه ۲ است.
با عرض پوزش، تصحیح شد !
سلام. به طور کلی این فرم سوالات خیلی راحت است و یک الگوریتم بازگشتی دارد. و من گزینه ۱ را رد می کنم تا روش کار را متوجه شوید :
روش کار هم اینگونه است :
گزینه ۱ :
[tex](12,8,5,10,9,20,14,15,18,13,16,19)[/tex]
چون پیمایش، پیشترتیب است گره ۱۲ ریشه است پس فورا پیمایش را به دوقسمت تقسیم می کنیم به این صورت که از گره بعد ریشه (یعنی ۱۲) هر گره ای که از ریشه کوچکتر بود را در زیر درخت چپ قرار می دهیم تا اینکه به اولین گره بزرگتر از ریشه برسیم، از آن گره به بعد، در زیر درخت راست قرار می گیرد و هیچ گره ای در زیر درخت راست، نباید از ریشه کوچکتر باشد :
[tex](8,5,10,9) --- (20,14,15,18,13,16,19)[/tex] (تا اینجا مشکلی وجود ندارد زیرا اعداد ۲۰ تا ۱۹، همگی از ۱۲ بزرگترند)
حالا مجددا با همین الگوریتم، ابتدا سمت چپ را چک می کنیم و بعد سمت راست را (البته ترتیب آن مهم نیست. در واقع الگوریتم، بازگشی است و الان با دو سوال، مانند سوال اول طرف هستیم) :
[tex](8,5,10,9)[/tex]
در درخت فوق، گره ۸ ریشه است و باز دو درخت خواهیم داشت :
[tex](5) --- (10,9)[/tex] (تا اینجا نیز مشکلی وجود ندارد زیرا اعداد ۱۰ و ۹، از ۸ بزرگترند)
در این لحظه با دو درخت که یکی تنها یک گره دارد (۵) و دیگری که تنها دو گره دارد (۱۰,۹) طرفیم که به آسانی می توان متوجه شد که مشکلی ندارند.
حال زیر درخت راست ریشه را بررسی می کنیم :
[tex](20,14,15,18,13,16,19)[/tex]
عدد ۲۰ ریشه است و این پیمایش به دو زیر درخت تقسیم می شود ولی زیر درخت راست آن تهی است زیرا همه اعداد ۱۴ تا ۱۹، از ۲۰ کوچکترند. پس تنها زیر درخت چپ آن می ماند که در مرحله بعد بررسی می کنیم :
[tex](14,15,18,13,16,19)[/tex] (تا اینجا نیز مشکلی نداریم چون همه اعداد ۱۴ تا ۱۹ از ۲۰ کوچکترند)
در این درخت، ۱۴ ریشه است و باز حالتی وجود دارد که یکی از زیر درخت ها تهی است و آن، زیر درخت سمت چپ است پس زیر درخت راست به این صورت است :
[tex](15,18,13,16,19)[/tex] (اما اینجا یک مشکل وجود دارد !!! همه اعداد باید از ۱۴ بیشتر باشد ولی ۱۳ اینطور نیست)
پس این گزینه رد است.
دوست عزیز در سوال من عدد ۶ ننوشتم عدد ۹ نوشتم
حالا میشه توضیح بدین دوباره ؟؟؟
آخه با این توضیح شما مسئله حل نمیشه همه چیز درست سرجاش قرار گرفته.
صورت سوال درسته سوالو از کتاب سنجش نوشتم.
بعد اتفاقا همین سوالو در پاسخ تشریحی پارسه هم دیدم سوال درسته.
شما نمیخوایین توضیح بدین .اگه قرار بود اون عدد ۶ باشه پس گزینه دوم غلط میشد چون ابتدای گزینه ها اعدادش مثل همه نگاه کنید.
(۰۴ آذر ۱۳۹۲ ۱۰:۳۶ ب.ظ)Morris نوشته شده توسط: سلام !!!!!
فکر می کنم مشکل شما در صورت سوال است
در صورت سوال عدد ۶ است و نه نیست.
صورت سوال :
![[تصویر: uzdu5hkf45o0yk8fg.jpg?size_id=5]](http://www.mediafire.com/convkey/3cb8/uzdu5hkf45o0yk8fg.jpg?size_id=5)
الان اینی که تو گذاشتی تو هیچ گزینه ۶نیست یکم دقت کن دوست عزیز
الان کنکور بود اشتباه می‌زدی
خوب من گزینه اول رد می‌کنم گزینه ۲ اصلاح شده گزینه اول هست
۱۲،۸،۵،۱۰،۹،۲۰،۱۴،۱۵،۱۸،۱۳،۱۶،۱۹
پیمایش پیشوندی پس به صورت VLR هست
۱۲ ریشه بعد کوچکتر از ۱۲ زیر درخت چپ و بزرگتر از ۱۲ زیر درخت راست پس میشه ۸،۵،۱۰،۹ و ۲۰،۱۴،۱۵،۱۸،۱۳،۱۶،۱۹
سمت اول که دوستمون موریس توضیح داد فقط بجای ۶ بذارید ۹ پس درسته زیر درخت چپ چون ۹،۱۰ از ۸ بزرگترن
در درخت فوق، گره ۸ ریشه است و باز دو درخت خواهیم داشت :
۹و۱۰ // ۵
حالا زیر درخت راست ابتدا ۲۰ میاد بعد ۱۴ فرزند چپ ۲۰ میشه چون کوچکتر، بعد ۱۵ که از ۱۴ بزرگتر پس فرزند راست ۱۴، حالا ۱۸ که میشه فرزند راست ۱۵، بعد ۱۳ میاد که چون از ۱۸ کوچک تره باید بذاریم فرزند چپ ۱۸ اما مشکل اینجاست که ۱۸ خودش جزو زیر شاخه راست ۱۵ و ۱۴ هست پس نباید از این دو کوچکتر باشه پس این گزینه غلطه
دقت کنید تمام عناصر بعد ۲۰ ازش کوچکترن پس همگی زیر درخت چپ ۲۰ هستن و ۲۰ زیر درخت راست نداره
دوستان ازتون ممنونم توضیحاتتون واقعا عالی بود و الان اشکال کارمو فهمیدم.
امیدوارم موفق باشید.