Оқытушы пәнінің ОҚУ-Әдістемелік кешені

б) қабатталған жақшалармен 
(A(B(D(I), E(J, К, L)), C(F(0), G(M, N), H(P) ))); 
в) графпен (сур. 18). 
 
 
Сур. 18 
Ағаш  граф  арқылы  неғұрлым  әдемі  көрінеді,  бірақ  аяғы  (түбірі) 
жоғарыда болады. Түйіндер деңгейлер бойынша орналасады. Түбір – нөлдік 
деңгей  және  т.с.с.  Ағаш  элементінің  максималды  деңгейі  оның  тереңдігі 
немесе биіктігі деп аталады. 
Ішкі  түйін  ұрпақтарының  саны  оның  дәрежесі  деп  аталады.  Барлық 
түйіндердің  максималды  дәрежесі  ағаштың  дәрежесі  болады.  Біздің  ағаш – 
үшінші дәрежелі ағаш. 
Түбірден  х  түйініне  қозғалу  үшін  өтетін  бұтақтар  немесе  қабырғалар 
саны  х-ке  өтетін  жол  ұзындығы  деп  аталады.  Түбірдегі 0 жол  ұзындығына 
тең,  оның  тікелей  ұрпақтары – 1 жолдың  ұзындығын  және  т.с.с.  Жалпы    i 
деңгейіндегі түйін i жолының ұзындығына ие. 
Ағаш  жолының  ұзындығы – оның  барлық  түйіндерінің 
ұзындықтарының  қосындысы.  Ол  сонымен  қатар  ішкі  жолдың  ұзындығы 
деп аталады. Біздің ағаш үшін жолдың ұзындығы 36-ға тең. Жодың орташа 
ұзындығы 
∑
=
⋅
=
n
i
i
ср
i
n
n
P
1
1
 
 
мұндағы n
i
 - i деңгейіндегі түйіндер саны ; n – элементтер саны. 
Егер  ағаштың  әрбір  түйінінің  бұтақтары  реттелген  болса,  онда  ағаш 
реттелген деп аталады: 
 
- 
әртүрлі 
реттелген 
ағаштар 

Ерекше  маңызды  рөл  атқаратын  екінші  дәрежелі  реттелген  ағаштар. 
Олар  бинарлы  немесе  екілік  ағаштар  деп  аталады.  Бинарлы  ағаштар – бұл 
элементтердің (түйіндердің) шекті жиыны, олардың әрбіреуі не бос (төменгі 
деңгеймен байланыспаған, ұрпақтары, яғни жапырақтары жоқ) болады, не екі 
әртүрлі – оң  және  сол  бинарлы  ішкі  ағаштары  бар  түбір  (түйін)  болып 
табылады. 
Дәрежесі  екіден  де  көп  болатын  ағаштар  қатты  тармақталған  деп 
аталады.  
Бинарлы ағаш мысалы – екіорынды операциялары бар арифметикалық 
өрнек,  мұнда  әрбір  операция – ішкі  ағаштар  ретіндегі  операндаларға  ие 
тармақталған түйін, мысалы өрнек (а + b / с) * (d - е* f), екілік ағаш түрінде 
келесі бейнеде көрсетіледі 
 
Кез  келген n-арлы  ағаш  оған  эквивалентті  бинарлы  ағашқа  қайта 
құрыла алады.. 
 
7.2 ЭЕМ-дегі ағаштардың көрсетілімі  
Ағаштарды  көрсету  мәселесін  қарастырайық.  Бұндай  тармақталған 
құрылымдарды  көрсету  сілтемелерді  қолдануды  жөн  көретіні  анық. 
Бекітілген  ағаштәрізді  құрылымдары  бар  айнымалыларды  бейнелеудің  мәні 
жоқ.  Бұның  орнына  түйіндер  бекітілген  құрылымдары  бар  айнымалылар 
сияқты  анықталады,  ал  олардың  арасындағы  байланыс – динамикалық 
көрсеткіштер  көмегімен.  Бұнда  ағаш  дәрежесі  әрбір  түйіннің  компонент-
көрсеткіштерінің  санын  анықтайды.  Бос  ішкі  ағашқа  сілтеме Nil арқылы 
белгіленеді. 
Осылайша,  біздің  ағаш – арифметикалық  өрнек – мынадай  типті 
компоненттерден тұрады деп есептеуге болады: 
TYPE NODE == RECORD 
INF:CHAR; 
LEFT, RIGHT: ^NODE  
END; 
және біздің ағаш келесі құрылыммен көрсетіледі (сур. 19). 

 
Сур.19 Ағаш мәліметтер құрылымы сияқты көрсетілген 
Бағдарламада  ағаштың  құрылуы TREE рекурсивті  функцияның 
көмегімен орындалады. n түйіндері бар және минималды биіктігі бар (яғни, 
соңғысынан  басқа  түйіндердің  максималды  санын  барлық  деңгейде 
орналастыру  керек)  ағаш  құру  керек  болсын.  Бұл  кезде  түйіндердің  мәні 
енгізілетін файлдан оқылатын N саны болады. 
TYPE REF =^ODE; 
NODE = RECORD 
KEY: integer;   { түйін құрамы - сан }  
LEFT, RJGHT: REF  
END; 
VAR N: INTEGER;       { ағаш түйіндерінің саны }  
ROOT: REF; болсын. 
Бұндай ағаш құру үшін барлық келіп түсетін түйіндерді әрбір түйіннен 
оң  және  сол  жаққа  бірдей  орналастыру  керек.  Бұндай  ағаш  идеалды 
балансталған деп аталады. 
TREE  процедурасы  әрекет  жасайтын  ережені  келесі  түрде  құруға 
болады: 
1) бір түйінді түбір ретінде алу керек; 
2) NL = N DIV 2 түйіндерімен  сол  ішкі  ағашты  құруды  аяқтау 
керек; 
3)  тура  сондай  әдіспен NR = N - NL – 1 түйіндерімен    оң  ішкі 
ағашты құру. 
Онда функция: 
FUNCTION TREE(N: INTEGER): REF; 
VARNEWNODE:REF; 
X, NL, NR : INTEGER; 
BEGIN 
IF N= 0 THEN TREE :=Nil 
ELSE BEGIN 
NL :=N div 2; NR := N - NL - 1; 
READ(x); NEW(NEWNODE); 
WITH NEWNODE
A
 DO BEGIN 
 KEY := X; LEFT := TREE(NL); RIGHT := TREE(NR); 

END; 
TREE:=NEWNODE; 
END  
END {TREE} 
 
7.3  Бинарлы  ағаштарға  қолданылатын  негізгі 
опреациялар 
Ағаштәрізді құрылымдарда үш негізгі операциялар орындалады: 
• керек түйінді табу үшін ағашты айналу (қарап шығу); 
• ағашқа түйінді немесе ішкі ағашты қосу; 
• ағаштан түйінді жою. 
 
Екілік ағашты айналу 
 
Ағашты  айналу  есебін  тұтас  тізбекті  процесс  деп  қарастырсақ,  онда 
түйіндерге  белгілі  бір  ретпен  қатысады  және  сызықты  орналасқан  деп 
есептеле алады. 
Бинарлы ағашты айналу үшін әдетте үш тәсілдің біреуі қолданылады: 
 
1)  жоғарыдан  төменге  айналу - А,  В,  С  (ішкі 
ағаштарға дейін түбірді қарап шығу); 
2) солдан оңға қарай айналу - В, А, С; 
3)  төменнен  жоғарыға  айналу - В,  С,  А  (ішкі 
ағаштардан кейін түбірді қарап шығу). 
Осындай  үш  процедураның  әрбіреуінде  әртүрлі 
реттегі келесі қадамдар бар: 
 
• ішкі ағаштың түбірін қарап шығу, 
•  сол ішкі ағашты айналу, 
•  оң ішкі ағашты айналу. 
Біздің  ағашты  айнала  отырып,  және  түйіндерде  орналасқан 
символдарды  олар  қандай  ретте  кездеседі,  сол  ретте  жазып  ала  отырып, 
келесі тізбектерді аламыз: 
1) жоғарыдан төменге:      *+a/bc-d*ef     ;      
 
            
 
(1) 
2) солдан оңға:         а + b / с * - е * f;                 
 
 
 
 
(2) 
3) төменнен жоғарыға:     abc/+def*-*;           
 
 
 
 
(3)  
Өрнектерді жазудың үш формасын алдық, олар 
(1) – префиксті жазба; 
(2)-  инфиксті  жазба  (бізге  үйреншікті  форма,  бірақ  операциялардың 
орындалуының ретін анықтауға арналған жақшаларсыз болса да); 
(3) – постфиксті жазба.