Inorder traversal: подробный пример работы алгоритма
Код алгоритма:
https://gist.github.com/codekrolik/6f8fef669154f75b6316
Тесты:
https://gist.github.com/codekrolik/ab806962e7e381c41cbf
В данном дереве ноды пронумерованы в соответствие с порядком обхода (inorder).
Ниже шаги алгоритма, а также состояние стека, доп.ноды и действия на каждом шаге.
| Шаг | Состояние доп.ноды | Состояние стека | Действие на данном шаге |
|---|---|---|---|
| 1 | 6 | - | Инициализация доп.ноды корнем дерева |
| 2 | 4 | 6 | доп.нода = левый ребенок 6 (4), 6 в стек |
| 3 | 2 | 6, 4 | доп.нода = левый ребенок 4 (2), 4 в стек |
| 4 | 1 | 6, 4, 2 | доп.нода = левый ребенок 2 (1), 2 в стек |
| 5 | NULL | 6, 4, 2, 1 | доп.нода = левый ребенок 1 (NULL), 1 в стек |
| 6 | NULL | 6, 4, 2 | доп.нода была NULL; процессим 1 (из стека), доп.нода = правый ребенок 1 (NULL) |
| 7 | 3 | 6, 4 | доп.нода была NULL; процессим 2 (из стека), доп.нода = правый ребенок 2 (3) |
| 8 | NULL | 6, 4, 3 | доп.нода = левый ребенок 3 (NULL), 3 в стек |
| 9 | NULL | 6, 4 | доп.нода была NULL; процессим 3 (из стека), доп.нода = правый ребенок 3 (NULL) |
| 10 | 5 | 6 | доп.нода была NULL; процессим 4 (из стека), доп.нода = правый ребенок 4 (5) |
| 11 | NULL | 6, 5 | доп.нода = левый ребенок 5 (NULL), 5 в стек |
| 12 | NULL | 6 | доп.нода была NULL; процессим 5 (из стека), доп.нода = правый ребенок 5 (NULL) |
| 13 | 8 | - | доп.нода была NULL; процессим 6 (из стека), доп.нода = правый ребенок 6 (8) |
| 14 | 7 | 8 | доп.нода = левый ребенок 8 (7), 8 в стек |
| 15 | NULL | 8, 7 | доп.нода = левый ребенок 7 (NULL), 7 в стек |
| 16 | NULL | 8 | доп.нода была NULL; процессим 7 (из стека), доп.нода = правый ребенок 7 (NULL) |
| 17 | 9 | - | доп.нода была NULL; процессим 8 (из стека), доп.нода = правый ребенок 8 (9) |
| 18 | NULL | 9 | доп.нода = левый ребенок 9 (NULL), 9 в стек |
| 19 | 10 | - | доп.нода была NULL; процессим 9 (из стека), доп.нода = правый ребенок 9 (10) |
| 20 | NULL | 10 | доп.нода = левый ребенок 10 (NULL), 10 в стек |
| 21 | NULL | - | доп.нода была NULL; процессим 10 (из стека), доп.нода = правый ребенок 10 (NULL) |
| 22 | NULL | - | выход из цикла, доп.нода == NULL, стек пуст |