트리(Tree)

트리(Tree)란?

---

 

트리의 개념

트리는 노드와 간선으로 이루어진 계층형 자료구조이다.

나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놨다해서 트리라는 이름이 붙여졌다.

계층 구조로 이루어져있기 때문에 데이터를 저장하고 탐색하기에 유용하다.

 

트리의 구성요소

노드

트리를 구성하는 요소

 

루트 노드

노드 중 가장 위에 있는 노드

 

엣지(간선)

노드와 노드를 연결해주는 선

단방향이며 루트 노드에서 각 노드까지의 경로는 유일하다.

 

노드 간의 관계

엣지로 연결된 노드들은 부모-자식 관계를 가지는데 상위에 있는 노드를 부모 노드, 하위에 있는 노드를 자식 노드라고 한다.

같은 부모 노드를 가지는 노드를 형제 노드라고 한다.

 

리프 노드

자식 노드가 없는 노드

 

차수

특정 노드에서 아래로 향하는 엣지의 갯수

 

이진트리 순회하기

---

 

이진 트리란?

위와 같이 차수가 2 이하인 트리를 말한다.

 

순회란?

어떤 데이터가 있을 때 그 데이터를 빠짐 없이 방문하는 것

종류는 다음과 같다.

• 전위 순회(Preorder): 현재 노드를 부모노드라고 생각했을 때 
  부모노드 --> 왼쪽 자식 노드 --> 오른쪽 자식 노드 순으로 방문
• 중위 순회(Inorder): 현재 노드를 부모노드라고 생각했을 때 
  왼쪽 자식 노드 --> 부모노드--> 오른쪽 자식 노드 순으로 방문
• 후위 순회(Postorder): 현재 노드를 부모노드라고 생각했을 때 
  왼쪽 자식 노드 --> 오른쪽 자식 노드 --> 부모노드 순으로 방문

부모노드를 방문하는 순서를 생각하면 외우기가 쉽다.

 

전위 순회(Preorder)

현재 노드를 부모노드라고 생각했을 때 부모노드 --> 왼쪽 자식 노드 --> 오른쪽 자식 노드 순으로 방문하는 것을 말한다.

 

과정

1.

• 루트 노드에서 부터 시작한다. 
• 현재 노드를 부모노드라고 생각하면 2-->7-->5 순으로 방문해야한다.
• 2를 방문처리하고 왼쪽 7로 간다.

2. 

• 7을 현재노드라고 생각하면 방문 순서는 7 --> 2 --> 6이다.
• 7을 방문처리하고 왼쪽 노드인 2로 간다.

3. 

• 2를 현재노드라고 생각하면 방문순서는 2 --> X --> X이다.
• 2를 방문처리하고 왼쪽, 오른쪽 노드가 없으므로 위로 돌아간다.
• 7에선 7 --> 2--> 6이므로 방문하지 않은 6으로 간다.

4. 

• 6을 현재노드라고 생각하면 방문순서는 6 --> 5 --> 11이다.
• 6을 방문처리하고 왼쪽 노드인 5로 간다.

5. 

• 5를 방문처리한다.
• 5는 자식노드가 없으므로 위로 돌아간다.
• 6에선 6-->5-->11이므로 11로 간다.

6.

• 11을 방문처리한다.
• 11은 자식 노드가 없으므로 상위노드로 다시 이동한다.
• 6, 7도 모든 노드에 대해 방문 했으므로 2로 간다.

7. 

• 위의 과정을 반복하면 5 --> 9 --> 4 순으로 방문하게 된다.

최종적인 방문순서는 

2 --> 7 --> 2 --> 6 --> 5 --> 11 --> 5 --> 9 --> 4가 된다.

전위 순회는 트리를 위에서부터 왼쪽으로 순차적으로 방문하기 때문에

트리를 복사할 때 사용된다.

---

중위 순회(Inorder)

현재 노드를 부모노드라고 생각했을 때 왼쪽 자식 노드 --> 부모노드--> 오른쪽 자식 노드 순으로 방문하는 것을 말한다.

1. 

• 루트노드부터 시작한다.
• 현재노드가 2이면 7 --> 2--> 5 순으로 방문해야하므로 7로 이동한다.
• 현재노드가 7이면 2 --> 7 --> 6 순으로 방문해야하므로 2로 이동한다.
• 현재노드가 2이면 X --> 2 --> X 순으로 방문해야하는데 왼쪽 노드가 없으므로 2를 방문처리한다.
  오른쪽 노드도 없으므로 다시 상위노드인 7로 이동한다.

2.

• 현재노드가 7이면 2 --> 7--> 6 순으로 방문해야하는데 2는 방문했으므로 7을 방문처리하고 6으로 간다.

3. 

• 현재노드가 6이면 5--> 6 --> 11순으로 방문해야하므로 5로 이동한다.
• 현재노드가 5이면 X --> 5 --> X순으로 방문해야 하는데 왼쪽 노드가 없으므로 5를 방문처리한다.
  오른쪽 노드도 없으므로 다시 상위노드인 6으로 이동한다.

4. 

• 현재노드가 6이면 5 --> 6--> 11순으로 방문해야하는데 5는 방문했으므로 6을 방문처리하고 11로 간다.

5. 

• 현재노드가 11이면 X --> 11 --> X순으로 방문해야하는데 왼쪽 노드가 없으므로 11을 방문처리한다
  오른쪽 노드가 없으므로 상위 노드로 이동한다
• 6, 7에서도 모든 노드를 방문했으므로 2로 이동한다.

6. 

• 나머지 노드에 대해서도 위와 같이 반복하면 5 --> 4 --> 9 순서대로 방문하게 된다.

최종적인 방문순서는 2 --> 7 --> 5 --> 6 --> 11 --> 5 --> 4 --> 9가 된다.

중위 순회는 트리가 이진탐색트리일때의 순서대로 방문하므로 

이진 탐색트리에서 정렬된 순서대로 값을 가져올 때 사용된다.

---

후위 순회(Postorder)

현재 노드를 부모노드라고 생각했을 때 왼쪽 자식 노드 --> 오른쪽 자식 노드 --> 부모노드 순으로 방문하는 것을 말한다.

 

1. 

• 루트노드부터 시작한다
• 현재노드가 2이면 7 --> 5 --> 2 순으로 방문해야하므로 7로간다.
• 현재노드가 7이면 2 --> 6 --> 11 순으로 방문해야하므로 2로간다.
• 현재노드가 2이면 X --> X --> 2 순으로 방문해야하는데 왼쪽, 오른쪽 노드가 없으므로 2를 방문처리한다.
• 다시 상위 노드인 7로 이동한다.

2. 

• 현재노드가 7이면 2 --> 6 --> 7 순으로 방문해야하는데 2는 방문했으므로 6으로 간다.
• 현재노드가 6이면 5--> 11 --> 6 순으로 방문해야하므로 5로 간다.
• 현재노드가 5면 X --> X --> 5 순으로 방문해야하는데 왼쪽, 오른쪽 노드가 없으므로 5를 방문처리한다.
• 다시 상위 노드인 6으로 이동한다.

3. 

• 현재노드가 6이면 5 --> 11 --> 6순으로 방문해야하는데 5는 방문했으므로 11로 이동한다.
• 현재노드가 11이면 X --> X --> 5 순으로 방문해야하는데 왼쪽 오른쪽 노드가 없으므로 5를 방문처리한다.
• 다시 상위노드인 6으로 이동한다.

4. 

• 현재 노드가 6이면 5 --> 11 --> 6 순으로 방문해야하는데 5와 11은 방문했으므로 6을 방문처리한다.
• 다시 상위노드인 7로 이동한다.

5.

• 현재 노드가 7이면 2 --> 6 --> 7 순으로 방문해야하는데 2와 6은 방문했으므로 7을 방문처리한다.
• 다시 상위 노드인 2로 이동한다.

6. 

• 나머지 노드에 대해 위의 과정을 반복하면 4 --> 9 --> 5 --> 2 순으로 방문하게 된다.

최종적인 방문순서는 2 --> 5 --> 11 --> 6 --> 7 --> 4 --> 9 --> 5 --> 2가 된다.

후위 순회는 리프노드부터 방문하므로

트리에서 노드를 삭제할 때 사용된다.

 

해당 포스트는 『코딩 테스트 합격자 되기 - 자바편』을 참고하여 작성되었습니다.