Chap 05. 트리

자료구조 with 윤성우 2021. 1. 29. 16:21

트리는 '계층적 관계'를 표현하는 자료구조이다.

트리는 '비선형' 자료구조이다.

● 노드 : 트리의 구성 요소에 해당하는 요소
● 간선 : 노드와 노드를 연결하는 선

● 루트 노드 : 트리에서 최상위에 존재하는 노드
● 단말 노드 : 아래로 다른 노드가 연결되어 있지 않는 노드

● 부모 노드 : 연결된 노드 중 상위에 있는 노드
● 자식 노드 : 연결된 노드 중 하위에 있는 노드
● 형제 노드 : 부모 노드가 같은 노드

서브 트리 : 하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리
서브 트리또한 서브트리로 이루어져 있다.(재귀적인 관계)

이진 트리의 조건

● 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 진다.
● 나뉘어진 두 서브 트리 모두 이진 트리어야한다. (재귀적)

트리는 루트노드부터 level 0으로 시작한다.
높이 : 루트노드에서 제일 아래 단말노드까지의 간선 수

트리의 높이 = 트리의 최대 level , 우측 예시의 트리 높이는 3

포화 이진 트리 : 모든 레벨에 노드가 꽉 찬 트리

완전 이진 트리 : '빈 틈 없이' '순서대로' 차곡차곡 채워진 트리