Postorder traversal: подробный пример работы алгоритма
Код алгоритма:
https://gist.github.com/codekrolik/916286dac0524caee4f6
Тесты:
https://gist.github.com/codekrolik/ab806962e7e381c41cbf
В данном дереве ноды пронумерованы в соответствие с порядком обхода (postorder).
Ниже шаги алгоритма, а также состояние стека и действия на каждом шаге.
| Шаг | Состояние стека | Действия на данном шаге |
|---|---|---|
| 1 | 10, 9, 5 | инициализация - корень (10) и его дети (9, 5) |
| 2 | 10, 9, 5, 4, 3 | берем 5, передобавляем 5 и его детей (4, 3) |
| 3 | 10, 9, 5, 4, 3, 2, 1 | берем 3, передобавляем 3 и его детей (2, 1) |
| 3 | 10, 9, 5, 4, 3, 2 | процессим 1 - лист дерева |
| 4 | 10, 9, 5, 4, 3 | процессим 2 - лист дерева |
| 5 | 10, 9, 5, 4 | процессим 3 - родитель 2 |
| 6 | 10, 9, 5 | процессим 4 - лист дерева |
| 7 | 10, 9 | процессим 5 - родитель 4 |
| 8 | 10, 9, 8, 6 | берем 9, передобавляем 9 и его детей (6, 8) |
| 9 | 10, 9, 8 | процессим 6 - лист дерева |
| 10 | 10, 9, 8, 7 | берем 8, передобавляем 8 и его детей (7) |
| 11 | 10, 9, 8 | процессим 7 - лист дерева |
| 12 | 10, 9 | процессим 8 - родитель 7 |
| 13 | 10 | процессим 9 - родитель 8 |
| 14 | - | процессим 10 - родитель 9 |
| 15 | выход из цикла, стек пуст |