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

이진트리란?

• 각 노드가 최대 2개의 자식을 갖는 트리이다.
• 하나의 노드의 자식이 3개 이상은 이진트리로 볼 수 없다.

왼 : 이진트리 성립 X / 오 : 이진트리 성립 O

이진트리의 특징

• 각 노드는 최대 2개의 자식을 가질 수 있으며, 왼쪽과 오른쪽 자식노드로 구분한다.
• 순회 방법은 전위 순회, 중위 순회, 후위 순회가 있다.

이진트리의 종류

---

전이진트리(Full Binary Tree or Strict Binary Tree)

모든 노드의 자식이 0개, 또는 2개의 자식을 갖는 트리를 말한다.

왼 : 전이진트리 성립 X / 오 : 전이진트리 성립 O

• 왼쪽 이미지의 경우, J의 노드가 K라는 자식을 갖고 있기 때문에 전이진트리가 성립하지 않는다.
• 오른쪽 이미지의 경우, 각 노드가 0개 또는 2개의 자식을 갖고있으므로 전이진트리가 성립한다.

완전이진트리(Complete Binary Tree)

마지막 레벨을 제외하고 모든 레벨의 노드가 채워져있음을 말한다.
마지막 레벨이 다 차있을 필요는 없으나 반드시 왼쪽부터 오른쪽으로 채워져있어야 한다.

왼 : 완전이진트리 성립 X / 오 : 완전이진트리 성립 O

• 왼쪽 이미지의 경우, 오른쪽부터 채워지지 않아 완전이진트리가 성립하지 않는다.
• 오른쪽 이미지의 경우, 오른쪽부터 잎노드가 채워져 완전이진트리가 성립한다.

포화이진트리(Perfect Binary Tree)

모든 노드가 두 개의 자식을 가지며, 모든 잎 노드가 동일한 레벨을 갖는 트리를 의미한다.
한마디로 전이진트리 이면서 완전이진트리여야한다.

왼 : 포화이진트리 성립 X / 오 : 포화이진트리 성립 O

• 왼쪽 이미지의 경우, 전이진트리와 완전이진트리가 성립은 하나 M 노드의 레벨이 다른 잎 노드와는 달라 포화이진트리가 성립하지 않는다.
• 오른쪽 이미지의 경우, 전이진트리와 완전이진트리가 성립하면서 모든 잎노드의 레벨이 같으므로 포화이진트리가 성립한다.

균형이진트리(Balanced Binary Tree)

왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1만큼 나는 트리를 말한다.

왼 : 균형이진트리 성립 X / 오 : 균형이진트리 성립 O

• 왼쪽 이미지의 경우, 트리의 레벨은 3이다. 허나 B를 기준의 서브트리의 레벨이 2지만, I는 서브트리의 레벨이 0이다. 따라서 두 서브트리의 레벨 차이는 2로 균형이진트리를 성립하지 않는다.
• 오른쪽 이미지의 경우, 트리의 레벨은 2이다. C 기준의 서브트리의 레벨이 1이고, F는 서브트리의 레벨이 0이다. 따라서 두 서브트리의 레벨 차이는 1로 균형이진트리를 만족한다.

편향이진트리(Skewed Binary Tree)

노드가 왼쪽이나 오른쪽 한 방향으로만 이루어진 트리를 의미한다.

왼 : 편향이진트리 성립 X / 오 : 편향이진트리 성립 O

• 왼쪽의 경우, 왼쪽 방향으로만 생기다가 마지막에 오른쪽 방향으로 D노드가 생겨 편향이진트리를 성립하지 않는다.
• 오른쪽의 경우, 왼쪽방향으로만 노드가 생겨 편향이진트리를 만족한다.

이진트리의 순회

이진트리를 모든 노드를 탐색하는 방법, 크게 전위 순회, 중위 순회, 후위 순회가 존재한다.

전위 순회(Preorder Traversal)

• 전위 순회는 루트를 먼저 순회 한 뒤, 왼쪽 서브 트리를 순회 한 후 오른쪽 서브 트리를 순회한다.
• 요약하면 Root -> Left -> Right이다.

중위 순회(Inorder Traversal)

• 중위 순회는 왼쪽 서브 트리를 먼저 순회 한 후, 루트를 순회하고 오른쪽 서브 트리를 순회한다.
• 이진트리에서 중위 순회를 통하여 정렬된 값을 얻을 수 있다.
• 요약하면 Left -> Root -> Right이다.

후위 순회(Postorder Traversal)

• 후위 순회는 왼쪽 서브 트리를 먼저 순회한 후, 오른쪽 서브 트리를 순회 하고 루트를 순회한다.
• 요약하면 Left -> Right -> Root이다.

출처 : [자료구조] 이진 트리 (Binary tree) 알아보기, 이진트리 위키백과, [CS - 자료구조] 이진 트리 (Binary Tree) 개념과 종류