2022.07.25 - [🧐 알고리즘] - [자료구조] 트리(Tree)
[자료구조] 트리(Tree)
트리(Tree) 🌲 노드,간선으로 이루어진 비선형 자료 구조 💡 트리의 특징 • 부모노드, 자식노드와 같이 계층구조로 표현되는 비선형 자료구조 • 탐색에 주로 사용 • 루트노드를 제외한 모든
kong-droid.com
트리 자료구조에 이어 이진트리에 대해 알아보겠습니다
🚀 이진트리 (Binary Tree)
영어에서 유추해볼 수 있듯이 이진트리는
💡 모든 노드가 자식 노드를 최대 2개를 가질 수 있는 트리
특징
• n개의 노드는 n-1의 간선을 가짐
• 자식노드는 공백이 될 수도 있음
• 레벨(a)에서 가질 수 있는 최대 노드의 갯수는 2ª
종류
📌 전 이진 트리 (Full Binary Tree)
- 각 레벨에 모든 자식노드가 0개 혹은 2개로 채워진 경우를 뜻합니다
📌 포화 이진 트리 (Perfect Binary Tree)
- 모든 리프 노드의 레벨이 같고, 리프 노드를 제외한 모든 노드들이 채워진 경우(노드들이 차수가 2인)를 뜻합니다
- 높이가 a인 경우, 이진트리가 가질 수 있는 노드의 갯수는 2ª-1인데, Perfect Binary Tree의 경우 가질 수 있는 모든 노드를 가지므로, 총 노드의 개수는 2ª-1 입니다
📌 완전 이진 트리 (Complete Binary Tree)
- 모든 리프 노드의 높이가 최대 1 차이가 나고 , 마지막 레벨을 제외한 노드들이 채워져 있는 경우입니다
- 노드는 왼쪽부터 채워져야합니다 , ⚠️ 오른쪽 사진은 완전 이진 트리가 아닙니다 ⚠️
궁금하신 점이나 의견이 있으시면 댓글 부탁드립니다 감사합니다 😊
'🧐 알고리즘' 카테고리의 다른 글
| [자료구조] 🚀 우선순위 큐 & 힙(Heap) (0) | 2022.07.27 |
|---|---|
| [자료구조] 트리(Tree) (0) | 2022.07.25 |
| [자료구조] 스택 , 큐 , 덱 (0) | 2022.07.17 |