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

트리란?

• 계층적인 구조를 나타내는 비선형 자료구조
• 부모-자식 관계의 노드로 이루어 진다.
• 트리는 하나의 루트 노드를 갖는다.
• 루트 노드는 0개 이상의 자식 노드를 갖는다.
• 자식 노드 또한 0개 이상의 자식노드를 갖는다.
• 노드들과 노드들을 연결하는 간선들로 구성되어 있다.

트리에는 사이클이 존재하지 않는다.

사이클 예시

---

트리의 용어

노드(Node): 트리의 구성요소
루트(Root): 부모가 없는 노드
레벨(Level): 트리의 각층 번호
높이(Height): 트리의 최대 레벨
차수(degree): 노드가 가지고 있는 자식 노드의 개수
단말노드(leaf node): 자식이 없는 노드 ( terminal 노드라고도 함 )

---

 

 

 

이진 트리

모든 노드가 2개 이하의
서브 트리를 가지고 있는 트리

 

---

이진트리의 성질

• n개 노드를 가진 이진트리는 n-1개의 간선을 가진다.
• 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2^h - 1개의 노드를 가진다.
• n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소 log2(n+1)

---

이진트리의 종류

포화이진트리: 트리의 각 레벨에 노드가 꽉 차있는 이진 트리

완전이진트리: 레벨 1부터 k-1까지는 노드가 모두 채워져있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 순서대로 채워져있는 이진트리

 

---

2022.12.12 - [📚 자료구조 및 알고리즘/트리] - [자료구조] 이진트리(Binary Tree) 구현

[자료구조] 이진트리(Binary Tree) 구현