이진트리의 순회(traversal)

  • 순회 : 이진 트리의 모든 노드를 방문하는 일

순회를 위한 작업 3가지

  1. D : 현재 노드를 방문하여 데이터를 읽는 작업
  2. L : 현재 노드의 ==왼쪽== 서브트리로 이동하는 작업
  3. R : 현재 노드의 ==오른쪽== 서브트리로 이동하는 작업

순회 종류 4가지 (노드 방문 순서에 따라)

  • 전위 순회 (Preorder Traversal)
  • 중위 순회 (Inorder Traversal)
  • 후위 순회 (Postorder Traversal)
  • 레벨 오더 순회(level-order Traversal)

① 전위 순회 (Preorder Traversal)

  • 현재 노드를 방문하여 데이터를 읽는 작업 D가장 먼저 수행하여 DLR 의 순서로 순회하는 방법

5933062B-210F-42B2-9598-48A93C29E100

PREORDER-TREE-WALK(x)
  if x != NIL
  	print key[x] // D
  	PREORDER-TREE-WALK(left[x])  // L
  	PREORDER-TREE-WALK(right[x]) // R

② 중위 순회 (Inorder Traversal)

  • 현재 노드를 방문하여 데이터를 읽는 작업 DLR의 사이에 수행하여 LDR 의 순서로 순회하는 방법

C879F19B-4D48-4E1A-B758-DA221FF7DEC6

INORDER-TREE-WALK(x)
  if x != NIL
  	INORDER-TREE-WALK(left[x])  // L
  	print key[x] // D
  	INORDER-TREE-WALK(right[x]) // R

③ 후위 순회 (Postorder Traversal)

  • 현재 노드를 방문하여 데이터를 읽는 작업 D가장 나중에 수행하여 LRD 의 순서로 순회하는 방법

94A0694C-FC49-438C-9E7B-4C065871A231

POSTORDER-TREE-WALK(x)
  if x != NIL
  	PREORDER-TREE-WALK(left[x])  // L
  	PREORDER-TREE-WALK(right[x]) // R
  	print key[x] // D

③ 레벨 오더 순회(level-order Traversal)

  • 레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로
  • 큐(queue)를 이용하여 구현

4A70D534-5BF2-41A7-9034-C4A042DB978B

LEVEL-ORDER-TREE-TRAVERSAL()
	visit the root:
	Q <- root	//Q is a queue
	while Q is not empty do
   		v <- dequeue(Q);
    	visit children of v;
    	enqueue childrenn of v into Q;

❗️문제

  • 전위, 중위, 후위, 레벨 오더 순회 경로 구하기

F6EE0838-0312-4738-AF51-12C893B731BE

  • 전위 순회 (Preorder Traversal)
    • A - B - D - H - I - E - J - K - C - F - L - G
  • 중위 순회 (Inorder Traversal)
    • H - D - I - B - J - E - K - A - L - F - C - G
  • 후위 순회 (Postorder Traversal)
    • H - I - D - J - K - E - B - L - F - G - C - A
  • 레벨 오더 순회(level-order Traversal)
    • A - B - C - D - E - F - G - H - I - J - K - L