[DS] 트리순회(Tree Traversal)란?

트리순회(Binary tree Traversal)란?

모든 node에 대하여 중복이나 누락없이 일정 순서로 모든 node를 방문하는 방법을 나타냅니다.

 

 

① 전위순회(preorder traversal)  -   node → left → right

현재 node를 방문 후 left, right node를 방문

② 중위순회(inorder traversal)     -    left → node → right

left node 방문 후 현재 node, right node를 방문

③ 후위순회(postorder traversal)  -  left → right → node

left, right node 방문 후 현재 node를 방문

 

 

아래 트리로 예를 들어보겠습니다.

 

 

① 전위순회(preorder traversal) 

a - b - d - e - c - f- g - h

 

② 중위순회(inorder traversal)  

d - b - e- a- c - g - f - h

 

③ 후위순회(postorder traversal)

d - e - b - g - h - f- c - a

 

 

 

◡̈