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;
Do'stlaringiz bilan baham: |