순회 (Traversal)

• 트리의 노드들을 체계적으로 방문하는 것
• 선형 자료구조(큐)에서의 순회는 하나의 방법만 존재하지만 이진 트리의 경우 비선형 자료구조 이므로 다양한 순회 방법이 존재함.

이진 트리의 기본 순회 종류

• 전위 순회 (Preorder Traversal)
  • 루트 → 왼쪽 자식 → 오른쪽 자식
• 중위 순회 (Inorder Traversal)
  • 왼쪽 자식 → 루트 → 오른쪽 자식
• 후위 순회 (Postorder Traversal)
  • 왼쪽 자식 → 오른쪽 자식 → 루트

전위 순회 (Preorder Traversal)

루트 → 왼쪽 서브트리 → 오른쪽 서브트리

preorder(x)

if x≠NULL    // x가 null이 아닐 때만 처리
	then print DATA(x);    // 루트(x) 노드 처리
			preorder(LEFT(x));    // 왼쪽 서브트리 방문
			preorder(RIGHT(x));    // 오른쪽 서브트리 방문

• Ex) 구조화된 문서 출력

중위 순회 (Inorder Traversal)

왼쪽 서브트리 → 루트 → 오른쪽 서브트리

inorder(x) 

if x≠NULL    // x가 null이 아닐 때만 처리
	then inorder(LEFT(x));    // 왼쪽 서브트리 방문 
			print DATA(x);    // 루트(x) 노드 처리
			inorder(RIGHT(x));    // 오른쪽 서브트리 방문

후위 순회 (Postorder Traversal)

왼쪽 서브트리 → 오른쪽 서브트리 → 루트

postorder(x)

if x≠NULL    // x가 null이 아닐 때만 처리
	then postorder(LEFT(x));    // 왼쪽 서브트리 방문
			postorder(RIGHT(x));    // 오른쪽 서브트리 방문
			print DATA(x);    // 루트(x) 노드 처리