[트리] 트리, 순회

📔  트리 구조

노드와 가지로 구성되고 각 노드는 가지를 통해 다른 노드와 연결된다.

 

트리에는 루트, 리프, 비단말 노드 , 자식, 부모, 형제, 레벨, 차수, 높이 등등의 용어들이 있다.

 

가장 위쪽에 있는 노드를 루트

 

가장 아래쪽에 있는 노드를 리프

 

루트에서 얼마나 멀리 떨어져 있는지 나타내는 레벨

 

각 노드가 갖는 자식의 수를 차수

 

루트에서 가장 먼 리프까지의 거리가 높이

 

 

 

📔 이진 트리의 검색 

 

너비 우선 검색

 

낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법

 

 

깊이 우선 검색

 

깊이 우선 검색은 리프에 도달 할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 한다.

 

 

 

 

깊이 우선 검색의 세가지 종류의 스캔 방법

 

 

 

노드 방문 -> 왼쪽 자식 -> 오른쪽 자식

 

위쪽 깊이 우선 탐색 그림의 전위 순회 순서

 

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