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

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ığı