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



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

#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

 10
20
21 
25
30


136
Бұтақты қарап шығу функциясын толығырақ қарастырамыз. Оған екінші 
параметр ретінде түйіннің қай деңгейде жатқанын анықтайтын бүтін айны-
малы беріледі. Түбір 0 деңгейінде орналасады. Бұтақ түбір сол жақта бола-
тындай етіліп, көлденең бағытта басып шығарылады (программа жұмысының 
нəтижесіне басыңызды солға қарай еңкейтіп қараңыз жəне оны 3.3-суретпен 
салыстырыңыз). Бұтақтың құрылымын бейнелеу үшiн түйiн мəнiнiң алдын-
да саны түйін деңгейіне пропорционал бос орындар шығарылады. Егер бос 
орындарды шығару циклін түсініктемеге алса, өсу ретімен сұрыпталған жиым 
бағана түрінде шығарылады. Бірнеше жолдан тұратын бұтақты қарап шығу 
функциясы кез келген өлшемдегі бұтақты басып шығара алады – тек стектің 
көлемі бұл ережеге бағынбайды.
Бұтақтан түйінді жою жеңіл орындалатын іс емес, өйткені жойыла-
тын түйін түбірлік болуы немесе оның құрамында ішкі бұтақтарға екі, бір 
сілтеме болуы, тіпті сілтемелер болмауы да мүмкін. Құрамындағы сілтемелер 
саны екіден артпайтын түйіндерді жою қиындық тудырмайды. Екі сілтемесі 
бар түйінді жойған кезде бұтақтың реттелген күйін сақтап қалу үшін, бұл 
түйінді оған кілті барынша ең жақын түйінмен алмастырады. Бұл оның сол 
жақ ішкі бұтағының ең оң жақтағы түйіні немесе оң жақ ішкі бұтағының ең 
сол жағындағы түйіні болуы мүмкін (мысалы, 3.3-суреттегі бұтақтан кілті 25 
болатын түйінді жою үшін оны 21 немесе 30 кілті бар түйіндерге алмастыру 
керек, ал 10 түйіні 20 немесе 8 түйіндеріне алмастырылады, т.с.с). Бұтақтан 
түйінді жою функциясының жүзеге асырылуы оқырманға өзіндік жұмыс 
ретінде қалдырылған. 


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




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

    Басты бет