최종 수정 : 25.1.2
이진 트리 순회
이진 트리에서 각 노드를 차례로 방문하는 것을 순회라고 한다. 트리의 노드가 n개일 때 각 노드를 배열로 표현한 후 순회하면 nPn의 가지수를 가진다. 그러나 트리의 특성상 이진 트리의 형태를 유지하여야 하므로 트리의 순회는 구별된다. 임의의 한 노드에서 순회하는 방법은 왼쪽 서브 트리로의 이동(L)과 현재의 노드를 방문(D)하거나 오른쪽 서브 트리로의 이동(R)이 있다. 노드를 순회할 때 방문하는 순서에 따라 중위(inorder) 순회, 후위 (postorder) 순회, 전위(preorder) 순회가 있다.
1. 종위 순회
종위 순회(inorder) 순회는 왼쪽 서브 트리, 루트와 오른쪽 서브 트리를 반복적으로 순회한다. 즉, 루트부터 출발하여 가운데를 지나가는 순서를 나열하는 방식이다.
2. 후위 순회
후위(postorder) 순회는 왼쪽 서브 트리, 오른쪽 서브 트리와 루트 순으로 반복적으로 순회한다. 즉, 루트부터 출발하여 가운데를 지나가는 순서를 나열하는 방식이다.
3. 전위 순회
전위 순휘(preorder)는 루트인 자신을 먼저 방문한 후, 왼쪽 서브 트리, 오른쪽 서브 트리 순으로 반복 순회한다. 즉, 루트부터 출발하여 왼쪽 서브 트리를 통해 내려가는 순서를 나열하는 방식이다.
참고
독학사 교재
댓글