---
title: "Inorder traversal: подробный пример работы алгоритма"
description: "Основной пост. Код алгоритма:https://gist.github.com/codekrolik/6f8fef669154f75b6316 Тесты:https://g..."
author: "codekrolik"
published: "2014-07-24T21:49:58+00:00"
modified: "2014-07-24T22:41:17+00:00"
locale: "ru"
canonical_url: "https://yvision.kz/post/inorder-traversal-podrobnyy-primer-raboty-algoritma-422694"
markdown_url: "https://yvision.kz/post/inorder-traversal-podrobnyy-primer-raboty-algoritma-422694/markdown"
site_name: "Yvision.kz"
---

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

> Основной пост. Код алгоритма:https://gist.github.com/codekrolik/6f8fef669154f75b6316 Тесты:https://g...

[Основной пост](http://codekrolik.yvision.kz/post/422553).

Код алгоритма: [https://gist.github.com/codekrolik/6f8fef669154f75b6316](https://gist.github.com/codekrolik/6f8fef669154f75b6316)

Тесты: [https://gist.github.com/codekrolik/ab806962e7e381c41cbf](https://gist.github.com/codekrolik/ab806962e7e381c41cbf)

![](https://storage.yvision.kz/images/user/codekrolik/1rKk83CHsbd23uzqYTGi1z51Msez3x.jpg)

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

---

Source: [https://yvision.kz/post/inorder-traversal-podrobnyy-primer-raboty-algoritma-422694](https://yvision.kz/post/inorder-traversal-podrobnyy-primer-raboty-algoritma-422694)