[JAVA/자료구조] 트리(Tree), 이진트리(Binary Tree) 란?

트리(Tree)

트리는 Node와 Edge로 이루어진 자료구조이다.

각 노드들이 나무가지처럼 브랜치( = 엣지, 링크)로 연결된 비선형적, 계층적 자료구조이다.

트리의 구조 (용어) 

노드와 에지

• 노드(Node) : 트리 구조에서 자료 값을 담고있는 단위 
• 에지(Edge) : 각 노드 간의 연결 선
• 루트 노드(Root) : 가장 위의 노드 (1)
• 잎새 노드(Leaf) : 자식이 없는 노드 (8), (9), (10) ...
• 내부 노드(Internal) : 잎새 노드를 제외한 모든 노드

노드 간의 관계

• 부모(Parent) : 연결된 두 노드 중 상위 노드 (2번 노드는 4번 노드의 부모 노드)
• 자식(Child) : 연결된 두 노드 중 하위 노드 (4번 노드는 2번 노드의 자식 노드)
• 형제(Sibling) : 같은 부모를 가지는 노드 ( 4번과 5번 노드는 형제 노드)

트리 구조 관련 

• 깊이(Depth) : 루트에서 해당 노드까지의 간선 수 (4번노드의 깊이는 2) ,  (12번 노드의 깊이는 3)
• 레벨(Level) : 트리의 특정 깊이를 가지는 노드의 집합( 4, 5, 6, 7번 노드는 level 2), (2, 3번 노드는 level 1)
• 높이(Height) : 트리에서 가장 큰 레벨 값 (위의 트리의 높이는 3)
• 크기(Size) : 자신을 포함한 자식노드의 개수 (1번노드에서의 크기는 15) , (5번노드에서의 크기는 3)
• 차수(Degree) : 각 노드가 가진 가지의 수 (1번 노드의 차수는 2 ) , ( 이 트리에서 모든 노드의 차수는 2이다.)
• 트리의 차수 : 트리의 노드들이 가진 차수 중 가장 큰 차수

---

트리의 특징

트리는 하나의 루트 노드를 갖는다.

• 루트 노드를 포함한 모든 노드는 0개 이상의 자식노드를 갖고 있다.

두 노드간의 이동 방법은 유일하다.

• 그래프의 경우 다른 노드로 이동하는 방법이 여러개 일 수 있지만, 트리는 그렇지 않다.
• 계층적 구조이기 때문에, 두 노드 사이에 이동경로는 한가지이다.
• 따라서 트리에는 사이클(cycle)이 존재할 수 없다.

비선형 자료구조로 계층적 관계를 표현한다.

• 디렉터리 구조, 조직도 등

하나의 Edge를 끊으면 2개의 Sub-Tree로 분리된다.

• Edge가 끊어지면, 끊어진 Edge를 기준으로 서로 다른 Tree가 된다.
• 즉, 하나의 Tree에서 모든 Node는 Edge로 연결되어있다.

---

이진트리(Binary Tree)

모든 노드들이 둘 이하의 자식을 가진 트리이다.

각 노드는 좌, 우를 구분한다.

---

이진트리의 종류

1. 포화 이진 트리 (Perfect Binary Tree)

모든 레벨에서 노드들이 가득 차있는 트리

• 포화 이진트리의 높이가 h 일때, 노드의 수는 2^(h+1) -1 개
• 포화 이진트리의 노드가 N개 일때, 높이는 logN개
• 이진 트리의 노드가 N개 일때, 최대 가능한 높이는 N (편향트리 일때)

---

2. 완전 이진 트리 (Complete Binary Tree)

마지막 레벨을 제외하고 노드들이 가득 차 있는 트리

(자식 노드가 하나만 있을 경우, 왼쪽부터 채워져야 한다.)

---

3. 정 이진 트리 (Full Binary Tree)

모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

---

4. 편향 트리(Skewed Binary Tree) = 사향 트리

한쪽으로 기울어진 트리

모든 노드가 왼쪽에만 있거나, 모든 노드가 오른쪽에만 있는 트리

---

5. 균형 이진 트리 (Balanced Binary Tree)

높이 균형이 맞는 트리

모든 노드의 좌우 서브 트리 높이가 1 이상 차이나지 않는 트리

---

이진 트리의 순회(Traversal)

순회 : 모든 노드를 빠뜨리거나, 중복하지 않고 모두 방문하는 연산

1. 전위 순회 (Preorder Traversal )

방문 순서 : 현재노드 > 왼쪽노드 > 오른쪽 노드

• 현재 노드 먼저 방문 한다.
• 왼쪽 노드가 있으면 왼쪽노드가 없는 노드가 나올때까지 계속 왼쪽노드를 방문한다. 
• 더이상 왼쪽노드를 찾을 수 없으면, 부모노드의 오른쪽 노드를 탐색한다.

---

2. 중위 순회 (Inorder Traversal)

방문 순서 : 왼쪽노드 > 현재노드 > 오른쪽 노드

• 왼쪽 끝의 노드를 찾아서 왼쪽으로 이동한다.
• 왼쪽 노드를 방문 후 부모노드(현재)를 방문한다.
• 부모노드의 오른쪽노드를 방문한다. 
• 만약 해당 노드의 왼쪽노드가 존재한다면 그 왼쪽노드 먼저 방문한다. (4번째 -> 6번째 노드의 경우)

---

3. 후위 순회 (Postorder Traversal)

방문 순서 : 왼쪽노드 > 오른쪽 노드 > 현재 노드

• 왼쪽 끝의 노드를 찾아서 왼쪽으로 이동한다.
• 왼쪽노드를 방문 후 형제노드(오른쪽) 노드를 방문한다.
• 왼쪽, 오른쪽 노드를 모두 방문했으면 부모노드(현재)를 방문한다.
• 만약 오른쪽노드를 방문했는데, 그 노드의 왼쪽 노드가 존재한다면 그 왼쪽 노드 먼저 방문한다. (3 -> 5 -> 4의 경우)

---

4. 레벨 순회(LevelorderTraversal)

방문 순서 : 위쪽 레벨부터 왼쪽노드 -> 오른쪽 노드 순으로 방문

BFS(Breadth-first search)와 같다.