Postorder traversal: подробный пример работы алгоритма

В данном дереве ноды пронумерованы в соответствие с порядком обхода (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		выход из цикла, стек пуст

Еще по теме