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

public void PostOrderTraversal(Action action)

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

Inarder usuli (yoki infix traversal)

• vazifasi: har bir tugunda belgilangan amalni bajarib, infix tartibida daraxt bo'ylab o'tadi.
• Murakkablik: O(n)
• Aylanib o'tish tartibi: 1, 2, 3, 4, 5, 6, 7, 8
• Infix traversal, biz tugunlarning qiymatlari bo'yicha daraxtni kesib o'tishimiz kerak bo'lganda qo'llaniladi. Yuqoridagi misolda daraxtda raqamli qiymatlar mavjud, shuning uchun biz ularni eng kichikdan kattagacha takrorlaymiz. Ya'ni, chap pastki daraxtlardan o'ngga ildiz orqali. Quyidagi misolda infixni o'tishning ikkita usuli ko'rsatilgan. Birinchisi rekursivdir. Har bir tugunda belgilangan amalni bajaradi. Ikkinchisi stekdan foydalanadi va to'g'ridan-to'g'ri takrorlash uchun iteratorni qaytaradi.

Public void InOrderTraversal(Action action)

• Public void InOrderTraversal(Action action)
• {
• InOrderTraversal(action, _head);
• }
• private void InOrderTraversal(Action action, BinaryTreeNode node)
• {
• if (node != null)
• {
• InOrderTraversal(action, node.Left);
• action(node.Value);
• InOrderTraversal(action, node.Right);
• }}
• public IEnumerator InOrderTraversal()
• {
• // Это нерекурсивный алгоритм.
• // Он использует стек для того, чтобы избежать рекурсии.
• if (_head != null)
• {

// Стек для сохранения пропущенных узлов.

• // Стек для сохранения пропущенных узлов.
• Stack stack = new Stack();
• BinaryTreeNode current = _head;
• // Когда мы избавляемся от рекурсии, нам необходимо
• // запоминать, в какую стороны мы должны двигаться.
• bool goLeftNext = true;
• // Кладем в стек корень.
• stack.Push(current);
• while (stack.Count > 0)
• {
• // Если мы идем налево...
• if (goLeftNext)
• {