개요
이번에는 자료구조 이진트리에 대해서 알아보도록 하겠습니다.
이진트리에 대해서 이해를 한 다음에 코드를 작성해 보도록 하겠습니다.
이진트리(Binary Tree)
개념과 구조
트리의 모든 노드의 차수를 2 이하로 제한하여 전체 트리의 차수가 2 이하가 되도록 정의하는 것입니다.
이진트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드만 가지게 되며,
부모 노드와 자식 노드 수와의 관계 -> 1:2
공백 노드도 자식 노드로 취급
0 ≤ 노드의 차수 ≤ 2
이진트리는 순환적 구성
노드의 왼쪽 자식 노드를 루트로 하는 왼쪽 서브 트리도 이진트리
노드의 오른쪽 자식 노드를 루트로 하는 오른쪽 서브 트리도 이진 트리
이진트리의 종류
포화 이진 트리(Full Binary Tree)
모든 레벨에 노드가 포화상태로 차 있는 이진 트리
높이가 h일 때, 최대의 노드 개수인 (2h+1-1)의 노드를 가진 이진트리
루트를 1번으로 하여 2h+1-1까지 정해진 위치에 대한 노드 번호를 가집니다.
완전 이진트리(Complete Binary Tree)
높이가 h이고 노드 수가 n개일 때 (단, n < 2h+1-1 ), 노드 위치가 포화 이진
트리에서의 노드 1번부터 n번까지의 위치와 완전히 일치하는 이진 트리
완전 이진트리에서는트리에서는 (n+1)번부터 (2h+1-1 ) 번까지번까지 노드는 모두 공백 노드
편향 이진트리(Skewed Binary Tree)
높이가 h일 때 h+1개의 노드를 가지면서 모든 노드가 왼쪽이나 오른쪽
중 한 방향으로만 서브 트리를 가지고 있는 트리
'알고리즘 & 자료구조 > 자료구조' 카테고리의 다른 글
| 자료구조 (이진트리 Binary Tree 검색 삽입) (0) | 2019.12.02 |
|---|---|
| 자료구조 (이진트리 노드사이즈 크기 구현) (0) | 2019.12.02 |
| 자료구조 (데크) (0) | 2019.12.02 |
| 자료구조 (연결 큐) (0) | 2019.12.02 |
| 자료구조 (원형 큐) (0) | 2019.12.02 |