Algoritmlarning xossalari Algoritmning asosiy xossalari. Algoritmning 5-ta asosiy xossasi bor: Diskretlilik Cheklilik


Download 1.05 Mb.
bet16/23
Sana06.04.2023
Hajmi1.05 Mb.
#1334689
1   ...   12   13   14   15   16   17   18   19   ...   23
Bog'liq
1 mavzu Algoritmlarning xossalari Algoritmning asosiy xossalari

Oldinga o'tish algoritmi:

  • Ildizga boring,

  • To'g'ridan-to'g'ri tartibda barcha pastki daraxtlarni chapdan o'ngga aylantiring.

Ushbu algoritm rekursivdir, chunki daraxtni kesib o'tishda o'tuvchi pastki daraxtlar mavjud va ular o'z navbatida bir xil algoritmdan o'tadilar.
Xususan, rasmdagi daraxt uchun. 3 va 4, to'g'ridan-to'g'ri o'tish tugunlarning ketma-ketligini beradi: A, B, C, D, E, F, G.
Olingan ketma-ketlik, daraxt bilan ichki qavs yordamida va Dyui o'nlik tizimida tasvirlanganda, shuningdek tepaliklar ro'yxati sifatida ko'rsatilganda yuqoridan pastga qarab tugunlarni ketma-ket chapdan o'ngga sanashga to'g'ri keladi.
Ushbu algoritm dasturlash tilida amalga oshirilganda, ildizni urish protsedura yoki funktsiya tomonidan ba'zi harakatlarning bajarilishiga to'g'ri keladi va pastki daraxtlarni bosib o'tish o'z-o'zidan rekursiv chaqiriqlarga mos keladi. Xususan, ikkitomonlama daraxt uchun (har bir tugundan ikkitadan ko'p bo'lmagan subtree kelib chiqadigan joyda) tegishli protsedura quyidagicha ko'rinadi:
// Preorder Traversal - to'g'ridan-to'g'ri buyurtma protsedurasining inglizcha nomi PreorderTraversal ((Argumentlar)); begin // DoSomething ((Argumentlar)) ildizi bo'ylab yurish; // Chap subtree bo'ylab harakatlaning, agar (Chap subtree mavjud bo'lsa), keyin PreorderTransversal ((Argumentlar 2)); // Agar o'ng tomondagi daraxtni kesib o'ting (Agar o'ng subtree bo'lsa), keyin PreorderTransversal ((3-argumentlar)); oxiri;
Ya'ni, avval protsedura barcha harakatlarni bajaradi va shundan keyingina barcha rekursiv chaqiriqlar paydo bo'ladi.
Orqaga o'tish algoritmi:

  • Chap pastki daraxtdan o'ting,

  • Ildizga boring,

  • Chapdagi keyingi subtree bo'ylab harakatlaning.

  • Ildizga boring,

  • va shunga o'xshash narsalar eng o'ng pastki daraxt o'tguncha.

Ya'ni, barcha kichik daraxtlar chapdan o'ngga o'tadi va ildizga qaytish ushbu o'tish joylari orasida joylashgan. Shakldagi daraxt uchun. 3 va 4 bu tugunlarning ketma-ketligini beradi: B, A, D, C, E, G, F
Tegishli rekursiv protsedurada harakatlar rekursiv chaqiriqlar orasida joylashtiriladi. Xususan, ikkilik daraxt uchun:
// Inorder Traversal - teskari tartibdagi InorderTraversal protsedurasining inglizcha nomi ((Argumentlar)); begin // Chap subtree bo'ylab harakatlaning, agar (Chap subtree mavjud bo'lsa) keyin InorderTraversal ((Argumentlar 2)); // DoSomething ((Argumentlar)) ildizi orqali yurish; // Agar o'ng tomondagi daraxtni kesib o'ting (Agar o'ng pastki daraxt mavjud bo'lsa), keyin InorderTraversal ((3-dalillar)); oxiri;

Download 1.05 Mb.

Do'stlaringiz bilan baham:
1   ...   12   13   14   15   16   17   18   19   ...   23




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling