트리란?
계층적 데이터 구조
정의
Root node: 가장 높은 곳에 있는 노드
Edge: 노드와 노드를 연결하는 선
Parent/Child node: edge로 연결된 노드 중 상위/하위 노드
Leaf node: 자식이 없는 노드
Degree(차수): 노드의 자식수 중 최대값
Level: 트리의 각 층, Root node가 level 1
Height: 트리의 최대 level
이진트리
공집합이거나 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 집합
이진트리의 서브 트리들은 모두 이진트리이어야 한다.
이진트리 분류
- 포화 이진 트리
트리의 각 레벨에 노드가 꽉 차있는 트리 - 완전 이진 트리
마지막 레벨에서 노드가 왼쪽부터 순 서대로 채워진 트리
특성
노드 수: n 개
edge: n-1 개
높이: log2(n+1)(올림) ~ n
높이: h
노드 수: h ~ 2^h-1
구현
배열구조: 완전이진트리가 아닐 시 빈칸이 발생 > 비효율적
연결된구조: 링크가 두 개만 있으면 표현 가능
이진트리의 연산
순회
전위 순회, 중위 순회, 후위 순회
전위순회: 루트 > 왼쪽 > 오른쪽
중위순회: 왼쪽 > 루트 > 오른쪽
후위순회: 왼쪽 > 오른쪽 > 루트