“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Misollardagi o'tish usullari har bir tugunda bajarilishi kerak bo'lgan harakatni belgilaydigan Action parametrini oladi. Shuningdek, usulning xatti-harakati va algoritmik murakkabligini tavsiflashdan tashqari, aylanib o'tish paytida olingan qiymatlar tartibi ko'rsatiladi.

• Misollardagi o'tish usullari har bir tugunda bajarilishi kerak bo'lgan harakatni belgilaydigan Action parametrini oladi. Shuningdek, usulning xatti-harakati va algoritmik murakkabligini tavsiflashdan tashqari, aylanib o'tish paytida olingan qiymatlar tartibi ko'rsatiladi.

Oldindan buyurtma berish usuli (yoki prefiksni chetlab o'tish)

• vazifasi: har bir tugunda belgilangan amalni bajarib, prefiks tartibida daraxtni kesib o'tadi. Murakkablik: O(n)
• Aylanib o'tish tartibi: 4, 2, 1, 3, 5, 7, 6, 8
• Prefikslarni kesib o'tishda algoritm avval chap pastki daraxtga, keyin esa o'ngga o'tishdan oldin joriy tugunning qiymatini oladi. Ildizdan boshlab, birinchi navbatda biz qiymatni olamiz 4. Keyin chap bola va uning bolalari xuddi shunday muomala qilinadi, keyin o'ng bola va uning barcha bolalari. Prefiks traversal odatda daraxtni tuzilishini saqlab qolgan holda nusxalash uchun ishlatiladi.

public void PreOrderTraversal(Action action)

• public void PreOrderTraversal(Action action)
• {
• PreOrderTraversal(action, _head);
• }
• private void PreOrderTraversal(Action action, BinaryTreeNode node)
• {
• if (node != null)
• {
• action(node.Value); PreOrderTraversal(action, node.Left); PreOrderTraversal(action, node.Right); }}

Postorder usuli (yoki postfiksdan o'tish)

• vazifasi: har bir tugunda belgilangan amalni bajarib, postfiks tartibida daraxtni takrorlaydi.
• Murakkablik: O(n)
• Aylanib o'tish tartibi: 1, 3, 2, 6, 8, 7, 5, 4
• Postfiksning o'tishi bilan biz chap pastki daraxtga, o'ng pastki daraxtga tashrif buyuramiz, so'ngra barcha bolalarni kesib o'tganimizdan so'ng, biz tugunning o'ziga o'tamiz. Postfix traversal ko'pincha daraxtni butunlay olib tashlash uchun ishlatiladi, chunki ba'zi dasturlash tillari xotiradan barcha tugunlarni aniq olib tashlashni yoki pastki daraxtni olib tashlashni talab qiladi. Ildiz bu holatda oxirgi marta qayta ishlanganligi sababli, biz tugunlarni olib tashlash uchun zarur bo'lgan ishni kamaytiramiz.