Mühazirə 1 Giriş Əsas anlayışlar. "Məlumat"

Ağaclar üzərində aparılan əsas əməliyyatlar

1. Ağacdan yan keçmə.

2. Altağacın ləğv edilməsi.
3. Altağacın araya salınması. 
Ağacdan yan keçməkdən ötrü aşağıdakı 3 prosedurları yerinə yetirmək lazımdır:
1.Ağac kökünün emalı.
2.Sol budağın emalı.
3.Sağ budağın emalı.
Bu prosedurların hansı ardıcıllıqla yerinə yetirilməsindən asılı olaraq, 3 növ ağacdan yan keçmə mümkün olur: 
1.Yuxarıdan aşağıya yan keçmə. Prosedurlar 1-2-3 ardıcıllığında yerinə yetirilirlər.
2.Soldan sağa yan keçmə. Prosedurlar 2-1-3 ardıcıllığında yerinə yetirilirlər.
3.Aşağıdan yuxarı yan keçmə. Prosedurlar 2-3-1 ardıcıllığında yerinə yetirilirlər.
Ağacdan yankeçmə istiqaməti şək.49-da verilmişdir.



Şək.Ağacdan yan keçmə istiqaməti

Şəkildən aşağıdakıları görmək olar:

A-B-C-E-D-F-G – yuxarıdan aşağı
C-B-D-E-F-A-G – soldan sağa
C-D-F-E-B-G-A – aşağıdan yuxarı
Qovşağa daxil olmağın hansı sayından sonra onun emala məruz qalmasından asılı olaraq, aşağıdakı 3 yan keçmələrdən biri həyata keçirilir:
-Əgər emal olunma qovşağa birinci dəfə daxil olduqdan sonra baş verirsə, onda bu yan keçmə yuxarıdan aşağıyadır,
-əgər ikinci dəfədən sonra baş verirsə - onda bu soldan sağadır,
-əgər üçüncü dəfə baş verirsə - onda bu aşağıdan yuxarıdır.
Altağacın ləğv edilmə əməliyyatı
Bu məqsədlə ləğv olunan altağacın birləşəcəyi qovşağı və bu altağacın kökünü göstərmək lazımdır.
Altağacın aradan götürülməsi ondan ibarət olur ki, ləğv olunan altağacla olan əlaqə qırılır, yəni, ləğv olunan qovşaq-köklə əlaqəli olan element göstəricisi “nil” vəziyyətinə quraşdırılır. Həmin qovşağın çıxış dərəcəsi bir vahid kiçildilir.
Altağacın araya salınma əməliyyatı
Bu halda araya salınan altağacın kökünün göstəricisini və altağacın asılı olacağı qovşağı bilmək lazımdır.
Bu qovşağın göstəricisini altağac kökünə quraşdırmaq, həmin qovşağın çıxış dərəcəsini isə bir vahid artırmaq lazımdır.
Bu zaman, ümumi halda, altağacın asıldığı qovşaq oğullarını yenidən nömrələmək lazım olacaqdır.
Binar axtarış ağacının yaradılması
Fərz edək ki, aşağıdakı açarlara malik olan elementlər verilmişdir: 14, 18, 6, 21, 1, 13, 15.
Bu açarlar üzrə nizamlanmış binar ağacı quraq.
Yaradılma alqoritmi belə olacaqdır:
read (key, rec)
tree = maketree (key, rec)
while not eof do
p = tree
q = tree
read (key, rec)
v = maketree (key, rec)
while p <> nil do
q = p
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
if key < k(q) then
left(q) = v
else
right(q) = v
endif
endwhile
return

Yuxarıda verilmiş alqoritmi yerinə yetirdikdən sonra şək.50-də göstərilən ağac alınacaqdır.

Şək.Binar axtarış ağacının yaradılması

Binar ağaclardan yan keçmənin rekursiv alqoritmləri

Altağaclardan yan keçmə ardıcıllığından asılı olaraq, ağaclardan yan keçməyin 3 növü vardır (şək.51):
1. Yuxarıdan aşağıya - А, В, С.
2. Soldan sağa və ya simmetrik keçmə - В, А, С.
3. Aşağıdan yuxarı - В, С, А.



Şək.Ağaclardan yan keçməyin növləri

Ən çox istifadə olunan ikinci üsuldur.

Alqoritmlər:
“yuxarıdan aşağı”
subroutine pretrave (tree)
if tree <> nil then
print info(tree)
pretrave(left(tree))
pretrave(right(tree))
endif
return
“simmetrik və ya soldan-sağa”
subroutine intrave (tree)
if tree <> nil then
intrave(left(tree))
print info(tree)
intrave(right(tree))
endif
return
Binar ağacdan yan keçmə rekursiyanı intrave (tree) proseduru misalında daha ətraflı izah edək.
Prosedur alqoritminin sətirlərni nömrəliyək.  
1. if tree <> nil
2. then intrave (left(tree))
3. print info (tree)
4. intrave (right (tree))
5.endif
6.return

Göstəriciləri belə işarə edək: t → tree; l → left; r → right.

Şək.52-də 3 qovşaqdan ibarət olan ən sadə ağacın qovşaqlarından yan keçdikcə intrave (tree) prosedurunun çağrılma ardıcıllığı təsvir olunmuşdur.

Şək.İntrave (tree) prosedurunun çağrılma ardıcıllığı