سلام
کدام یک از دنباله های زیر که هریک نشان دهنده ترتیب درج عناصر از چپ به راست در یک درخت دودویی جستجوی تهی است ، درخت زیر را تولید نمی کند؟شکل سوالو در زیر پیوست کردم.
۱)CAEGDBF
۲)CABEGDF
۳(CEGAFDB
۴(CEBGADF
جواب گزینه ۴ است.
انواع پیمایش درخت جستجوی دودویی چه صورته؟(به غیر از inorder , perorder ,postorde)
اگه میشه یکی توضیح کاملی در این سوال بده من متوجه بشم.
(۰۴ آذر ۱۳۹۲ ۰۹:۴۴ ب.ظ)tarane1992 نوشته شده توسط: سلامسلام
کدام یک از دنباله های زیر که هریک نشان دهنده ترتیب درج عناصر از چپ به راست در یک درخت دودویی جستجوی تهی است ، درخت زیر را تولید نمی کند؟شکل سوالو در زیر پیوست کردم.
۱)CAEGDBF
۲)CABEGDF
۳(CEGAFDB
۴(CEBGADF
جواب گزینه ۴ است.
انواع پیمایش درخت جستجوی دودویی چه صورته؟(به غیر از inorder , perorder ,postorde)
اگه میشه یکی توضیح کاملی در این سوال بده من متوجه بشم.
اگر دقت کنید متوجه می شوید در مورد گزینه ۴ این مراحل را اریم
اول c به عنوان ریشه انتخاب میشود
حالا E بر طبق خواص درخت جستجوی دودویی به عنوان فرزند راست c انتخاب می شود
حالا B بر طبق خواص درخت جستجوی دودویی به عنوان فرزند چپ c انتخاب می شود و تا همینجا کافی هست تا گزینه ۴ را رد کنیم چون طبق شکل درخت پیوست شده فرزند چپ C نود A هست نه B
گزینه ۴ رد میشه چون برخلاف سایر گزینه ها B زودتر از A امده
یعنی منظورتون اینه در پیمایش کردن این سوال باید دقت کنیم فرزند زودتر از پدر نیاد درسته؟
خوب در گزینه های دیگه هم بعد از ریشه باید فرزند چپ و راست قرار بگیره .مهم نیست که بعد از هر ریشه حتما فرزند چپ و راست با هم باشن یکیشونوم باشه کافیه درسته؟
گزینه ۳ رو میتونید بگید چرا درسته ؟؟
(۰۴ آذر ۱۳۹۲ ۱۰:۴۸ ب.ظ)tarane1992 نوشته شده توسط: یعنی منظورتون اینه در پیمایش کردن این سوال باید دقت کنیم فرزند زودتر از پدر نیاد درسته؟
خوب در گزینه های دیگه هم بعد از ریشه باید فرزند چپ و راست قرار بگیره .مهم نیست که بعد از هر ریشه حتما فرزند چپ و راست با هم باشن یکیشونوم باشه کافیه درسته؟
گزینه ۳ رو میتونید بگید چرا درسته ؟؟
همان طور که خودتان گفتید باید دقت کنیم فرزند زودتر از پدر نیاد. در مورد سوال دوم مکان و ترتیب قرار گرفتن فرزندان بعد از پدر در دنباله های متفاوت فرق می کند.
و اما در مورد گزینه ۳
ابتدا ریشه c درج می شود
بعد طبق خواص درخت دودویی نود e به عنوان فرزند راست c در درخت درج می شود
بعد طبق خواص درخت دودویی g به عنوان فرزند راست e در درخت درج می شود
بعد طبق خواص درخت دودویی a به عنوان فرزند چپ c در درخت درج می شود
بعد طبق خواص درخت دودویی f به عنوان فرزند چپ g در درخت درج می شود
بعد طبق خواص درخت دودویی d به عنوان فرزند چپ e در درخت درج می شود
و در اخر طبق خواص درخت دودویی b به عنوان فرزند راست a در درخت درج می شود
برای حل این گونه مسائل بهتر هست که قدم به قدم درخت حاصله از هر دنباله را رسم کنید و با درخت عنوان شده در صورت سوال مقایسه کنید.
جواب این سوال هم بسیار ساده است نیاز به پیمایش نیست
۲نکته فقط باید دقت کنید: اول: والد(پدر) در ورودی باید قبل از فرزندانش قرار بگیره دوم:فرزندان بعد والد به هر ترتیبی میتوانند باشند
اینجا در گزینه ۴ گره b زودتر از a که پدرش بود آمد پس غلطه
have good time