درخت دودويي جست و جو

[mehdi58]

با سلام
لطفا در مورد اين تيپ تستها كمي توضيح دهيد .
با تشكر

فرض كنيد اعداد 1 تا 1000 در يك درخت دودويي جست و جو ذخيره شده اند و ما مي خواهيم عدد 363 را پيدا كنيم . كداميك از ترتيب هاي زير از چپ به راست ، نمي تواند بيانگر ترتيب دسترسي به عناصر درخت در اين جست و جو باشد ؟
1) 363-245-912-240-911-202-925
2)363-362-258-898-244-911-220-924
3)363-397-344-330-398-401-252-2
4)363-278-381-382-266-219-387-399-2

[cups_of_java]

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

ریشه 925 بوده. چون 363 کوچکتره پس فرزند چپ رو انتخاب کرده. مقدار فرزند چپ و همه فرزندان زیرش (اعدادی که می بینی در ادامه لیست) باید از 925 کوچکتر باشه. یعنی اگه عددی بزرگتر از 925 الان تو لیست گزینه یک بود همینجا می گفتیم این غلطه! خب 202 شد فرزند چپ که 363 از اون بزرگتره پس به راست می ریم. فرزند راست 911 هست. (باید از 202 بزرگتر و از 925 کوچکتر می بود، که هست) 363 از 911 کوچکتره پس می ریم چپ. فرزند چپ 240 هست (از 911 کوچکتره، از 202 بزرگتره و از 925 کوچکتر. اگه به مسیری که اومدیم نگاه کنی می بینی چپ، راست، چپ بوده! پس این عدد هم درسته تا اینجا) حالا 363 از 240 بزرگتره پس باید بریم راست. پس فرزند راست 240، 912 هستش. خب! 912 از 240 بزرگتره پس می تونه راستش باشه اما ما الان تو زیر درخت سمت چپ 911 هستیم. پس همه اعداد بعد 911 باید ازش کوچکتر باشن! پس 912 نمی تونسته اینجا باشه! و این گزیته غلطه!


همین لم رو استفاده کن تا اونی که درست هست رو پیدا کنی. راه سریع حل این تست از همون توضیحات به راحتی قابل تشخیصه!