Программалау оқулық Алматы, 012 Қазақстан Республикасы Білім жəне ғылым министрлігінің «Оқулық»
жүктеу/скачать 3.66 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- 1, 6, 8, 10, 20, 21, 25, 30
- 30, 25, 21, 20, 10, 8, 6, 1
| function way_around ( бұтақ ){
way_around ( сол жақ ішкі бұтақ ) түбірге жету way_around ( оң жақ ішкі бұтақ ) } 1 Жедел жадыда ұяшықтар адрестерінің өсу реті бойынша сызықтық түрде орналасқанын, ал бұтақ тек мəліметтерді логикалық ұйымдастыру əдісі екендігін ұмытпаған жөн. 2 Сол жақ жəне оң жақ ішкі бұтақтардағы түйіндер санының айырмасы бірден артпайтын теңдестірілген бұтақтың биіктігі түйіндер санының екілік логарифміне тең. Сызықтық тізімді құрамындағы əрбір түйіннің бірден артық емес сілтемелері болатын ерекше бинарлы бұтақ ретінде қарастыру мүмкіндігі бар. Тізім үшін орташа іздеу уақыты тізімнің ұзындығының жартысына тең. 133 3.3-сурет. Бинарлы бұтақ Бұтақты басқа реттілікпен де қарап шығуға болады, мысалы, алдымен түбір, содан кейін ішкі бұтақтарға көшу арқылы, мұндайда келтірілген функ- ция нəтижесінде (шығысында) кілттердің реттелген тізбегін алуға мүмкіндік береді, өйткені алдымен сол жақ ішкі бұтақта орналасқан кілттері кіші төбелер қарастырылады. Төменде 3.3-суретте көрсетілген бұтақты қарап шығу нəтижесі берілген: 1, 6, 8, 10, 20, 21, 25, 30 Егер бұтақтарды қарап шығу функциясындағы оны алғашқы пайдалану оң жақ ішкі бұтаққа бағытталаған болса, онда оны қарап шығу нəтижесі басқаша болады: 30, 25, 21, 20, 10, 8, 6, 1 Осылайша, іздеу бұтағын мəндерді сұрыптау үшін де қолдануға болады. Бұтақтарды қарап шығуда түйіндер жойылмайды. Бинарлы бұтақтар үшін анықталған операциялар: □ бұтаққа түйін қосу; □ бұтақ бойынша іздеу; □ бұтақты қарап шығу; □ түйінді жою. Əрбiр рекурсивті алгоритм үшiн оның рекурсивтi емес баламасын құруға болады. Төмендегі программада бұтақтан іздей отырып түйін қосуға арналған рекурсивті емес функция жəне бұтақтарды қарап шығуға арналған рекурсивті функция жүзеге асырылған. Бірінші функция берілген кілт бойынша іздеу 134 жүргізеді. Егер элемент табылса, функция осы элементке нұсқауышты қайтарады, кері жағдайда элементті бұтақтың тиісті жеріне орналастырады жəне оған нұсқауышты қайтарады. Элементті қосу үшін бұтақ бойымен бір қадам кейін өткен жолды есте сақтау керек жəне жаңа элементті қосу оның ата тегінің 1 оң немесе сол жақ ішкі бұтағына орындалатынын білу қажет. Программа бүтін сандар жиымынан бұтақ қалыптастырады жəне оны экранға шығарады. жүктеу/скачать 3.66 Mb. Достарыңызбен бөлісу:
|