Шаг-5: Если существует прошивочный узел, делаем его текущим узлом.
Шаг-6: Если все узлы напечатаны, завершаем работу, иначе переходим к шагу 1.
| | |
Список
| |
шаг-1
|
A имеет левого потомка то есть B, который ещё не посещён, так что помещаем B в наш «список посещённых узлов» и B становится текущим узлом.
|
B
| |
шаг-2
|
B также имеет левого потомка D, которого нет в списке посещённых узлов. Помещаем D в список посещённых и делаем текущим.
|
B D
| |
шаг-3
|
У узла D нет левого потомка, так что печатаем D, затем проверяем правого потомка. D не имеет правого потомка, так что смотрим на прошитую ссылку. Узел имеет прошивку к узлу B, так что делаем B текущим.
|
B D
|
D
|
шаг-4
|
B имеет левого потомка, но он уже посещён. Таким образом, печатаем B, затем проверяем на наличие правого потомка, но его нет, так что мы делаем прошитый узел (то есть A) текущим.
|
B D
|
D B
|
шаг-5
|
A имеет левого потомка B, но он уже посещён, так что печатаем A и проверяем наличие правого потомка. Узел A имеет правого потомка C и он отсутствует в списке посещённых узлов, так что мы добавляем его в этот список и делаем текущим.
|
B D C
|
D B A
|
шаг-6
|
C имеет узел E в качестве левого потомка и этот узел ещё не посещён, так что добавляем узел E в список и делаем его текущим.
|
B D C E
|
D B A
|
|
Do'stlaringiz bilan baham: |
