Tree 순회방법 3가지

Tree 구조에 대해서 순회하는 방법에는 3가지가 있다.

 

1) 전위 운행

2) 중위 운행

3) 후위 운행 

 

 

전위 운행부터 알아보도록 하자. 

 

Preorder 경우에는  Root, left, right 의 순서이다.

Pre(이전의, 미리)의 느낌을 생각해서 뿌리, 왼쪽, 오른쪽을 생각하자.

뿌리 먼저 방문

그러면 이 tree구조에 대해서는 어떻게 되는지 보자.

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

 

다음은 중위 운행에 알아보도록 하자. 

 

Inorder 경우에는   left, Root, right 의 순서이다.

왼쪽 하위 노드 방문 후 뿌리 방문

그러면 이 tree구조에 대해서는 어떻게 되는지 보자.

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

 

 

다음은 후위 운행에 알아보도록 하자.

Postorder 경우에는  left, right, Root 의 순서이다.

하위 노드 모두 방문 후 뿌리 방문

그러면 이 tree구조에 대해서는 어떻게 되는지 보자.

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