[CS] 트리 / 이진 트리(Binary Tree) / 완전 이진 트리(Complete Binary Tree)

트리 (Tree)

트리 구조(Tree)란 그래프의 일종으로, 한 노드에서 시작해서 다른 저엄드을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다. 트리는 계층형 비선형구조이다.  여기서 비선형 구조란 선형 구조와 다르게 데이터가 계층 혹은 망으로 구성되어 있다. 아래는 트리에서 사용하는 용어이다.

 

• Node : 트리에서 데이터를 저장하는 요소
• Level : 최상위 노드를 Level0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이로 표현
• Root Node : 트리 최상단 Level에 있는 노드
• Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
• Child Node: 어떤 노드의 하위 레벨에 연결된 노드
• Leaf Node : Child Node가 없는 노드
• Sibling Node : 동일한 Parent Node를 가진 노드
• Depth : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

---

이진 트리(Binary Tree)

이진트리는 각각 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조이다.

크기가 9이고, 높이가 3인 이진 트리(출처: 위키백과)

---

완전 이진 트리(Complete Binary Tree)

완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 위치해 있는것이 특징이다. 마지막 레벨 h에서 1부터 2^h-1 개의 노드를 가질 수 있다.

---

참고

트리 구조 - 위키백과, 우리 모두의 백과사전

 

이진 트리 - 위키백과, 우리 모두의 백과사전