트리 : 순회

들어가기 전에

트리의 노드에 숫자를 매기는 순회에 대해 살펴보도록 하겠습니다.

 

학습 목표

여러 가지 순회 방법을 이해하고 직접 해볼 수 있습니다.

 

핵심 단어

• 순회

트리:순회

 

Trees Traversal

Pre order traversal:

- visit root node

- visit left child

- visit right child

 

In order traversal:

- visit left child

- visit root

- visit right child

 

Post order traversal:

- visit left child

- visit right child

- visit root

 

전위 순회 (Pre order traversal): 루트 노드에서 시작하여 왼쪽 자식 노드에 갔다가 오른쪽 자식 노드로 가는 순회 방법입니다. 다른 모든 노드를 지나기 전에 루트 노드를 방문하기 때문에 이름에 전(Pre)이 들어갑니다.

 

중위 순회 (In order traversal): 왼쪽 자식 노드에서 시작하여 루트 노드에 갔다가 오른쪽 자식 노드로 가는 순회 방법입니다.

 

후위 순회 (Post order traversal): 왼쪽 자식 노드에서 시작하여 오른쪽 자식 노드에 갔다가 루트 노드로 가는 순회 방법입니다.

 

너비 우선 선회/레벨 순서 순회 (Breadth first traversal/level order traversal): 가장 위에 있는 노드에서 시작하여 왼쪽에서 오른쪽으로 가는 순회 방법입니다.

 

 

생각해보기

1) 전위, 중위, 후위 순회는 반복적인 규칙을 갖고 있습니다. 이를 코드로 구현하려면 어떻게 해야 할까요?

 

나의 생각 : 보통 반복적인 규칙을 갖고 있으면 재귀방식으로 구현합니다.

 

출처 : https://www.boostcourse.org/cs204/lecture/626048?isDesc=false