Вітаю! Підкажіть, будь ласка, як пройти бінарне дерево ітератором? (Preorder. Inorder. Postorder). Я створила алгоритми для проходження дерева в правильному порядку для preorder і postorder. але дуже погано розумію, як можна працювати з ітератором на прикладі дерева. (Я маю право займати в пам'яті тільки константну величину, тобто не можна використовувати хешсет, Арран лист і інші структури з динамічно мінливої довжиною).
заданий 28 Березня '14 о 18:16
Відразу уточнимо, що в вузлах дерева повинні зберігатися посилання на їх батьків. У Ітератор будемо зберігати тільки посилання на поточний вузол. Код буде на С ++, але його нескладно переписати на Java.
Якщо у поточного вузла є лівий нащадок, то переходимо в нього. В іншому випадку, якщо є правий нащадок, то переходимо в нього. Якщо нащадків немає, то треба піднятися вгору по ланцюжку батьків, поки ми не зустрінемо вузол, у якого ми ще не відвідали правого нащадка, тобто такий вузол, в який ми прийдемо зліва в процесі підйому. Правий нащадок цього вузла буде наступним при обході.
Першим в обході буде корінь дерева.
Якщо у поточного вузла є праве піддерево, то наступним вузлом буде самий лівий вузол в цьому поддереве. В іншому випадку треба підніматися вгору по ланцюжку батьків, поки ми не зустрінемо батька, в якого ми прийдемо з лівого боку. Цей батько і буде наступним вузлом.
Першим в обході буде самий лівий вузол дерева.
Найпростіший випадок. Переходимо в батька. Якщо ми прийшли з лівого нащадка, і існує правий нащадок, то переходимо в самий лівий вузол правого піддерева. В іншому випадку залишаємося в батьку.
Знову ж таки, першим в обході буде самий лівий вузол дерева.