[자료구조] 9. 이진트리(binary tree)

공부한 날짜: 2021.09.30

 

-이진트리: 모든 노드가 최대 2개의 자식을 가질 수 있는 트리

예시) 수식이진트리(수식을 트리 형태로 표현하여 계산하게 함), 이진 탐색 트리(아주 빠른 데이터 검색을 가능하게 함)

ㄴ 이진트리의 특징: 노드의 최대차수 2(가능한 값 0,1,2)

ㄴ 이진트리의 종류: 포화이진트리, 완전 이진트리,높이 균형 트리,완전 높이 균형 트리

 

-포화 이진트리: 모든 노드가 자식을 둘씩 가지고 있는 이진트리. 잎 노드들이 모두 같은 깊이에 존재한다는 특징을 가짐

-완전 이진트리: 잎 노드들이 트리의 왼쪽부터 차곡차곡 채워진 것이 특징

-높이 균형 트리: 루트 녿를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1이상 차이나지 않는 이진트리

-완전 높이 균형 트리: 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위트리의 높이가 같은 이진트리

 

-이진트리의 순회 :트리 내의 노드들 사이를 돌아다니는 것을 말함 

순회에는 전위순회,중위순회,후위순회가 있다 

 

1. 전위 순회: 루트 노드부터 잎 노드까지 아래 방향으로 방문하는 순회

(1) 루트 노드부터 시작해서 아래로 내려오면서

(2) 왼쪽 하위 트리를 방문하고 끝나면

(3) 오른쪽 하위트리 방문

 

2.중위 순회: 왼쪽 하위 트리부터 오른쪽 하위 트리 방향으로 방문하는 순회

(1) 왼쪽 하위 트리부터 시작 : 가장 왼쪽의 '잎 노드'부터 시작한다는 말

(2) 루트

(3) 오른쪽 하위 트리 

 

노드-부모노드-형제노드 순서 

중위 순회가 쓰이는 예: 수식트리

 

3.하위 순회:

(1) 왼쪽 하위트리부터 시작

(2) 오른쪽 하위트리

(3) 루트노드 순서