트리 순회

<트리 순회>
-트리의 모든 노드를 한번씩 방문하는 것.
-모든 노드를 순회하는 방법엔 크게 세가지가 있다.(트리구조가 계층적구조라는 특별한 특징때문에)
-전위 순회, 중위 순회, 후위 순회

-모두 노드를 순회할때 왼쪽부터 오른쪽으로 조회한다는 공통점이 있다.

 

 

전위 순회 (preorder traverse)
-ABDHIEJK  CFLMGNO
-가장 먼저 방문하는 노드는 루트이다.
-루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.
-부모 노드가 제일 먼저 방문되는 순회방식이다.
-주로 트리를 복사할때 사용.

 

중위 순회 (inorder traverse)
-HDIBJEKA LFMCNGO
-제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다. 
-부모 노드가 서브 트리의 방문 중간에 방문되는 순회방식이다.
-이진 탐색 트리의 오름차순으로 값을 가져올때 쓰인다.

 

후위 순회 (postorder traverse)
-HIDJKEB LMFNOGCA
-루트를 가장 마지막에 순회힌다.
-제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한뒤, 제일 마지막에 루트를 방문한다.
-트리를 삭제할때 사용한다. (자식노드가 먼저 삭제되어야 상위 노드를 삭제할수있기 때문이다.)

---

 

레벨 순회 (levelorder traverse)
-ABCDEFGH
-루트를 방문하는 기준으로 순회를 하는 것이 아닌 트리의 레벨 기준으로 노드들을 방문하는 순회방법이다.
-루트 노드를 시작으로 아래로 뻗어 나가며 노드들을 방문하며 루트 노드의 레벨이 1레벨이라고 했을때 아래로 내려갈수록 레벨은 증가하는 특징을 보인다.
-동일한 레벨에 여러 노드가 존재할 경우 왼쪽에서 오른쪽 순서로 노드를 방문한다.

---

#순회방식을 나누는 이유
-모든 노드를 방문하기 위해서는 일정한 조건이 필요하고, 트리 구조를 유지보수하거나 특정 목적을 위해서도 순회 방법에 대한 정의는 필수적으로 필요하다.

 

---

출처

코드스테이츠