Как в этом случае работает обход почтовых заказов DFS? - PullRequest
0 голосов
/ 20 сентября 2019

Так что DFS PreOrder Traversal имеет для меня смысл.Я просто не понимаю, как этот обход DFS Postorder является правильным.Как мне этого добиться?

Вот график, о котором я говорю

1 Ответ

1 голос
/ 20 сентября 2019

Трассировка прохождения после заказа с использованием стека.Не добавляйте детей, которые уже посещены.

Visit root, add children
Stack: [A]
Visited: []

Pop A, add children
Stack: [B, C, D]
Visited: [A]

Pop D, add children
Stack: [B, C, F]
Visited: [A, D]

Pop F, add children
Stack: [B, C, E, H]
Visited: [A, D, F]

Pop H, add children
Stack: [B, C, E, G, I]
Visited: [A, D, F, H]

Pop I, add children
Stack: [B, C, E, G]
Visited: [A, D, F, H, I]

Pop G, add children
Stack: [B, C, E]
Visited: [A, D, F, H, I, G]

Pop E, add children
Stack: [B, C]
Visited: [A, D, F, H, I, G, E]

Pop C, add children
Stack: [B]
Visited: [A, D, F, H, I, G, E, C]

Pop B, add children
Stack: []
Visited: [A, D, F, H, I, G, E, C, B]

Nothing to pop. Done!

...