'중위 순회(Inorder Traversal)'에 해당되는 글 1건

  1. 2013.05.28 이진 트리의 순회 (Traversal)


순회의 세 가지 방법

이진 트리를 대상으로 하는 대표적인 순회의 세 가지 방법은 다음과 같다.

# 전위 순회(Preorder Traversal) : 루트 노드를 먼저 방문.

# 중위 순회(Inorder Traversal) : 루트 노드를 중간에 방문.

# 후위 순회(Postorder Traversal) : 루트 노드를 마지막에 방문.


이렇듯 이진 트리를 순회하는 대표적인 방법은 다음 내용을 기준으로 세 가지로 나뉜다.

즉, Root Node 를 언제 방문하느냐에 따라 달라진다.


Left -> Root -> Right

루트 노드는 중간에 방문이 이뤄지기 때문에 이러한 방식의 순회를 가리켜 '중위 순회' 라 한다.


Left -> Right -> Root

루트 노드는 마지막에 방문을 하게 되므로, 이러한 방식의 순회를 가리켜 '후위 순회' 라 한다.


Root -> Left -> Right

루트 노드는 첫 번째로 방문을 하게 되므로, 이러한 방식의 순회를 가리켜 '전위 순회' 라 한다.


루트 노드와 이를 부모로 하는 두 자식 노드를 놓고, 한쪽 방향으로 순서대로 방문을 하면 된다.

※ 이진 트리는 그 구조가 재귀적이다.







'Programming > Data Structure' 카테고리의 다른 글

트리(Tree)  (0) 2013.05.21
덱을 기반으로 큐를 구현  (0) 2013.01.30
덱 (Deque)  (0) 2013.01.30
큐의 연결 리스트 기반 구현  (0) 2013.01.29
큐의 배열 기반 구현  (0) 2013.01.29
Posted by scii
: