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



Pdf көрінісі
бет208/642
Дата30.03.2022
өлшемі3,66 Mb.
#29231
түріПрограмма
1   ...   204   205   206   207   208   209   210   211   ...   642
Байланысты:
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

   8 

 10

       20

             21 

   25  

        30


136

Бұтақты қарап шығу функциясын толығырақ қарастырамыз. Оған екінші 

параметр ретінде түйіннің қай деңгейде жатқанын анықтайтын бүтін айны-

малы беріледі. Түбір 0 деңгейінде орналасады. Бұтақ түбір сол жақта бола-

тындай етіліп, көлденең бағытта басып шығарылады (программа жұмысының 

нəтижесіне басыңызды солға қарай еңкейтіп қараңыз жəне оны 3.3-суретпен 

салыстырыңыз). Бұтақтың құрылымын бейнелеу үшiн түйiн мəнiнiң алдын-

да саны түйін деңгейіне пропорционал бос орындар шығарылады. Егер бос 

орындарды шығару циклін түсініктемеге алса, өсу ретімен сұрыпталған жиым 

бағана түрінде шығарылады. Бірнеше жолдан тұратын бұтақты қарап шығу 

функциясы кез келген өлшемдегі бұтақты басып шығара алады – тек стектің 

көлемі бұл ережеге бағынбайды.

Бұтақтан түйінді жою жеңіл орындалатын іс емес,  өйткені жойыла-

тын түйін түбірлік болуы немесе оның құрамында ішкі бұтақтарға екі, бір 

сілтеме болуы, тіпті сілтемелер болмауы да мүмкін. Құрамындағы сілтемелер 

саны екіден артпайтын түйіндерді жою қиындық тудырмайды. Екі сілтемесі 

бар түйінді жойған кезде бұтақтың реттелген күйін сақтап қалу үшін, бұл 

түйінді оған кілті барынша ең жақын түйінмен алмастырады. Бұл оның сол 

жақ ішкі бұтағының ең оң жақтағы түйіні немесе оң жақ ішкі бұтағының ең 

сол жағындағы түйіні болуы мүмкін (мысалы, 3.3-суреттегі бұтақтан кілті 25 

болатын түйінді жою үшін оны 21 немесе 30 кілті бар түйіндерге алмастыру 

керек, ал 10 түйіні 20 немесе 8 түйіндеріне алмастырылады, т.с.с). Бұтақтан 

түйінді жою функциясының жүзеге асырылуы оқырманға өзіндік жұмыс 

ретінде қалдырылған. 





Достарыңызбен бөлісу:
1   ...   204   205   206   207   208   209   210   211   ...   642




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

    Басты бет