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

Онда іздеудің қарапайымдалған процедурасы былай жазылады: 
FUNCTION LOC(X: INTEGER; Т: REF): REF; 
BEGIN 
S^.KEY:=X; 
WHILE T^.KEY <>Х DO 
IF X < T^KEY THEN Т := T^.LEFT 
ELSE Т := T^.RIGHT; 
LOC:=T 
 END; 
Егер  тамыры  Т  болатын  ағашта  Х  мәні  бар  кілт  табылмаса,  онда  бұл 
жағдайда LOC(X, Т) S мәнін,  яғни  бөгетке  сілтемені  қабылдайды. S-ке 
сілтеме өзіне Nil сілтемесінің ролін алады. 
 
Ағашқа жаңа түйін қосу 
Ағашқа  жаңа  түйін  қосудың  көрнекті  мысалы  ретінде  жиілік  сөздігін 
құру  болып  табылады.  Бұл  жағдайда  сөздер  тізбегі  берілген,  әрбір  сөздің 
кездесу  жиілігін  табу  керек.  Бұл  әрбір  бос  ағаштан  бастап,  әр  сөз  ағаштан 
ізделінетіндігін  білдіреді.  Егер  ол  табылса,  оның  кездесу  санағышы  бір 
көрсеткішке  ұлғаяды,  табылмаса – осы  сөз  ағашқа  енгізіледі  (санағыштың 
бастапқы мәні 1-ге тең. Мұны ағаштан қосып іздеу деп атауға болады. 
Қарапайымдылық  үшін  бастапқы  мәтіннен  сөздер  ерекшеленіп,  бүтін 
сандармен кодталған және енуші файлда орналасқан деп болжаймыз. 
Типтер былай сипатталған болсын: 
TYPE REF = ^WORD; 
WORD = RECORD 
KEY: INTEGER; 
COUNT: INTEGER; 
LEFT, RIGHT: REF  
END; 
Кілттердің F бастапқы файлы бар деп есептейік, ал ROOT айнымалысы 
іздеу ағашының тамырын білдірсін: 
RESET (F); 
WHILE NOT EOF(F) DO BEGIN  
READ (F, X); 
SEARCH (X, ROOT)  
END; 
Мұнда SEARCH (X, ROOT) – іздеу процедурасы. Оның сипаттамасы: 
PROCEDURE SEARCH (X: INTEGER; VAR P: REF); 
BEGIN IF P = Nil THEN BEGIN  
NEW(P); 
WITH P^ DO BEGIN 
KEY :=X; COUNT:=1; 
LEFT:=Nil; RIGHT:=Nil  
END 
 END ELSE 

IF X < P^.KEY THEN SEARCH(X, P^.LEFT) ELSE  
IF X > P^.KEY THEN SEARCH(X, P^.RIGHT) ELSE 
P^.COUNT := P^.COUNT +1  
END {SEARCH } 
P  параметрі  параметр-мән  ретінде  емес,  параметр-айнымалы  ретінде 
жіберілетіндігіне назар аударайық. Бұл маңызды, себебі оған сілтеменің жаңа 
мәні беріледі. 
Осыны  есепке  ала  отырып,  сонымен  қоса  сөздердің  кілттері INPUT 
файлынан алынады десек, негізгі бағдарламаны былай жазуға болады : 
BEGIN 
ROOT :=Nil; 
WHILE NOT EOF DO BEGIN 
 READ (K); 
SEARCH (K, ROOT); 
END; 
PRINTTREE (ROOT, 0) 
 END. 
ROOT және К айнымалылары  
VAR ROOT: REF; K: INTEGER; деп сипатталу керек 
Салыстыру үшін SEARCH процедурасының версияларын рекурсияның 
қолданылуынсыз  жасайық.  Қосуды  жасау  үшін  өтілген  жолды  кем  дегенде 
алдындағы бір қадамды есте сақтау керек. Кезекті қосылатын компонентаны 
дұрыс  қосу  үшін  оның  арғы  аталарына  сілтемеміз  болу  керек  және  оның 
бағыныңқы  ағаштардың  қайсысы:  сол  жақ  немесе  оң  жақ  болып 
қосылатынын білуіміз керек. Ол үшін екі айнымалы енгізіледі: Р2 мен D: 
PROCEDURE SEARCH (X: INTEGER; ROOT: REF); 
VAR PI, P2: REF; D: INTEGER; 
BEGIN P2 := ROOT; PI := P2^.RIGHT; D :=1; 
WHILE (PI <> Nil) AND (D <> 0) DO BEGIN  
P2:=P1; 
IFX
BEGIN P1:=P1^.LEFT; D:=-1  
END  
ELSE IF X>P1^.KEY THEN 
BEGIN P1:=Pl^.RIGHT; D := 1 
 END  
ELSE D := 0  
END; 
IF D = 0 THEN Pl^.COUNT := Pl^.COUNT + 1 
ELSE BEGIN  
NEW(Pl); 
WITH P1^ DO BEGIN 
KEY := X; LEFT :=Nil; 
RUGHT :=Nil; COUNT := 1  
END; 

IF D < 0 THEN P2^.LEFT := P1 
ELSE IF D > 0 THEN P2^.RIGHT := P1  
END  
END; 
Мұнда  екі  сілтеме  қолданылады:  Р1  және P2, іздеу  процесінде P2 
әрқашан    P1^  предикатына  сілтейді.  Бұл  шартты  іздеу  басында 
қанағаттандыру  үшін root сілтейтін  қосымша  фиктивті  элемент  енгізіледі. 
Нақты
 
іздеу  ағашының  басы ROOT^.RIGHT сілтемесімен  белгіленеді. 
Сондықтан бағдарлама келесі операторлардан басталу керек 
NEW(ROOT); ROOT^.RIGHT :=Nil; 
(бастапқы мән берудің орнына ROOT := Nil) 
 
 
Ағаштан жою 
Жою – қосуға  кері  амал.  Реттелген  кілттері  бар  ағаштан  Х  кілті  бар 
түйінді жою алгоритмін құру керек. Элементті жою әдетте қосу сияқты оңай 
емес. 
Ол жойылатын элемент терминалды түйін болса немесе бір де ұрпағы 
болмаған жағдайда оңай болады (21-сурет) 
 
                 а)                                   б) 
Тудырушы элементке                Тудырушы элементте сілтеме  
Nil 
сілтемесі 
енгізіледі          
 
жойлатын 
түйіннен 
туындаған             
элементке ауысады 
21-сурет Қарапайым жағдайда ағаштан жою 
 
Екі ұрпағы бар элементтерді жою кезінде қиыншылықтар туындайды, 
өйткені  біз  екі  бағытта  бір  сілтемені  қолдана  алмаймыз.  Бұл  жағдайда 
жойылушы  элементті  оның  сол  жақ  бағыныңқы  ағашының  оң  жағындағы 
элементке  ауыстыру  керек  немесе  оның  оң  жақ  бағыныңқы  ағашының  сол 
жағындағы  элементке  ауыстыру.  Ондай  элементтердің  бірден  көп  ұрпағы 
болмайтыны анық (22-сур.). 
 

 
22-сурет Ағаштан жою 
Жою процесін DELETE рекурсивті процедурасымен көрсетуге болады. 
Оның үш жағдай бар: 
1) X-ке тең кілті бар компонента жоқ; 
2) X-ке тең кілті бар компонентаның бірден көп емес ұрпағы бар; 
3) X-ке тең кілті бар компонентаның екі ұрпағы бар.  
PROCEDURE DELETE (X: INTEGER; VAR P: REF); 
VAR Q: REF; 
PROCEDURE DEL(VAR R: REF); 
BEGIN 
IF R^.RIGHT <> NIL THEN DEL(R^.RIGHT) 
 ELSE BEGIN Q^.KEY := R^.KEY; Q^COUNT := R^.COUNT; 
Q := R; R := R^.LEFT END  
END { DEL }  
BEGIN { DELETE } 
IF P = NIL THEN WRITELN(‘ берілген кілтпен сөз табылған жоқ ')  
ELSE 
IF X < P^.CEY THEN DELETE(X, P^.LEFT) 
ELSE 
IF X > P^.KEY THEN DELETE (X, P^.RIGHT) 
ELSE BEGIN { P сілтемесі бойынша жою} 
 Q:=P; 
IF Q^.RIGHT = NIL THEN P := Q^.LEFT  
ELSE 
IF Q^.LEFT = NIL THEN P := Q^.RIGHT  
ELSE DEL(Q^.LEFT); 
DISPOSE(Q)  
END  
END {DELETE } 
DEL  қосымша  рекурсивтік  процедурасы  үшінші  жағдайда  ғана 
шақырылады. Ол жойылатын Q^ түйінінің сол жақ бағыныңқы ағашының ең 
оң бұтағы бойымен «төмен түсіп», Q^-ғы бар ақпаратты (кілт пен санағыш)