📔 트리 구조
노드와 가지로 구성되고 각 노드는 가지를 통해 다른 노드와 연결된다.
트리에는 루트, 리프, 비단말 노드 , 자식, 부모, 형제, 레벨, 차수, 높이 등등의 용어들이 있다.
가장 위쪽에 있는 노드를 루트
가장 아래쪽에 있는 노드를 리프
루트에서 얼마나 멀리 떨어져 있는지 나타내는 레벨
각 노드가 갖는 자식의 수를 차수
루트에서 가장 먼 리프까지의 거리가 높이
📔 이진 트리의 검색
너비 우선 검색
낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법
깊이 우선 검색
깊이 우선 검색은 리프에 도달 할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 한다.
깊이 우선 검색의 세가지 종류의 스캔 방법
더보기
노드 방문 -> 왼쪽 자식 -> 오른쪽 자식
위쪽 깊이 우선 탐색 그림의 전위 순회 순서
A -> B -> D -> H -> E -> I -> J -> C -> F -> K -> L -> G
더보기
왼쪽 자식 -> 노드 방문 -> 오른쪽 자식
위쪽 깊이 우선 탐색 그림의 중위 순회 순서
H -> D -> B -> I -> E -> J -> A -> K -> F -> L -> C -> G
더보기
왼쪽 자식 -> 오른쪽 자식 -> 노드 방문
위쪽 깊이 우선 탐색 그림의 후위 순회 순서
H -> D -> I -> J -> E -> B -> K -> L -> F -> G -> C -> A