Программалау оқулық Алматы, 012 Қазақстан Республикасы Білім жəне ғылым министрлігінің «Оқулық»
жүктеу/скачать 3.66 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Node *pv = new Node; pv->d = d; pv->left = 0; pv->right = 0; return pv; }
- // Тегінің оң жақ ішкі ағашына қосу: prev->right = pnew; return pnew; } //
| #include struct Node{ int d; Node *left; Node *right; }; Node * fi rst(int d); Node * search_insert(Node *root, int d); void print_tree(Node *root, int l); //------------------------------------------------ int main(){ int b[] = {10, 25, 20, 6, 21, 8, 1, 30}; Node *root = fi rst(b[0]); for (int i = 1; i<8; i++) search_insert(root, b[i]); print_tree(root, 0); return 0; } //------------------------------------------------ // Бұтақтың алғашқы элементін қалыптастыру Node * fi rst(int d){ Node *pv = new Node; pv->d = d; pv->left = 0; pv->right = 0; return pv; } //------------------------------------------------ // Қоса отырып іздеу Node * search_insert(Node *root, int d){ Node *pv = root, *prev; bool found = false; while (pv && !found){ prev = pv; if (d == pv->d) found = true; else if (d < pv->d) pv = pv->left; else pv = pv->right; 1 «Іздей отырып қосу алгоритміне сенiмсiздiк білдіру – заңды құбылыс» – классикалық «Алгорит- мы + структуры данных = программы» кітабының [8] авторы Н.Вирт. 135 } if (found) return pv; // Жаңа түйін құру: Node *pnew = new Node; pnew->d = d; pnew->left = 0; pnew->right = 0; if (d < prev->d) // Тегінің сол жақ ішкі ағашына қосу: prev->left = pnew; else // Тегінің оң жақ ішкі ағашына қосу: prev->right = pnew; return pnew; } //---------------------------------------------- // Бұтақты қарап шығу void print_tree(Node *p, int level){ if (p){ // сол жақ ішкі бұтақты шығару: print_tree(p->left, level + 1); for (int i = 0; i // ішкі бұтақтың түбірін шығару: cout << p->d << endl; // оң жақ ішкі бұтақты шығару: print_tree(p->right, level + 1); } } Бұтақтан іздеуге арналған ағымдағы нұсқауыш pv арқылы, оның ата-тегіне нұсқауыш prev арқылы белгіленген, pnew айнымалысы бұтаққа қосылатын түйін үшін жады бөлуде қолданылады. Бір айнымалыны ( prev ) есте сақтап, жаңа түйінді қосу кезінде ол қай ішкі бұтаққа қосылатынын анықтайтын опе- раторларды қайталау арқылы ол рекурсиясыз орындалды. 3.3-суретте бейнеленген бұтақ үшін программаның жұмыс істеу нəтижесі төмендегідей болады: 1 6 8 10 20 21 25 30 136 Бұтақты қарап шығу функциясын толығырақ қарастырамыз. Оған екінші параметр ретінде түйіннің қай деңгейде жатқанын анықтайтын бүтін айны- малы беріледі. Түбір 0 деңгейінде орналасады. Бұтақ түбір сол жақта бола- тындай етіліп, көлденең бағытта басып шығарылады (программа жұмысының нəтижесіне басыңызды солға қарай еңкейтіп қараңыз жəне оны 3.3-суретпен салыстырыңыз). Бұтақтың құрылымын бейнелеу үшiн түйiн мəнiнiң алдын- да саны түйін деңгейіне пропорционал бос орындар шығарылады. Егер бос орындарды шығару циклін түсініктемеге алса, өсу ретімен сұрыпталған жиым бағана түрінде шығарылады. Бірнеше жолдан тұратын бұтақты қарап шығу функциясы кез келген өлшемдегі бұтақты басып шығара алады – тек стектің көлемі бұл ережеге бағынбайды. Бұтақтан түйінді жою жеңіл орындалатын іс емес, өйткені жойыла- тын түйін түбірлік болуы немесе оның құрамында ішкі бұтақтарға екі, бір сілтеме болуы, тіпті сілтемелер болмауы да мүмкін. Құрамындағы сілтемелер саны екіден артпайтын түйіндерді жою қиындық тудырмайды. Екі сілтемесі бар түйінді жойған кезде бұтақтың реттелген күйін сақтап қалу үшін, бұл түйінді оған кілті барынша ең жақын түйінмен алмастырады. Бұл оның сол жақ ішкі бұтағының ең оң жақтағы түйіні немесе оң жақ ішкі бұтағының ең сол жағындағы түйіні болуы мүмкін (мысалы, 3.3-суреттегі бұтақтан кілті 25 болатын түйінді жою үшін оны 21 немесе 30 кілті бар түйіндерге алмастыру керек, ал 10 түйіні 20 немесе 8 түйіндеріне алмастырылады, т.с.с). Бұтақтан түйінді жою функциясының жүзеге асырылуы оқырманға өзіндік жұмыс ретінде қалдырылған. жүктеу/скачать 3.66 Mb. Достарыңызбен бөлісу:
|