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: |