Программалау оқулық Алматы, 012 Қазақстан Республикасы Білім жəне ғылым министрлігінің «Оқулық»



Pdf көрінісі
бет128/466
Дата20.07.2022
өлшемі3,66 Mb.
#37798
түріПрограмма
1   ...   124   125   126   127   128   129   130   131   ...   466
Байланысты:
pavlovskaia-jogargy-dengeili

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
оң немесе сол жақ ішкі бұтағына орындалатынын білу қажет.
Программа бүтін сандар жиымынан бұтақ қалыптастырады жəне оны 
экранға шығарады.


Достарыңызбен бөлісу:
1   ...   124   125   126   127   128   129   130   131   ...   466




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет