[TIL]Day 16

넓이 우선 순회의 원칙

수준(level)이 낮은 노드를 우선으로 방문,
같은 수준의 노드들 사이에는 부모노드의 방문 순서에 따라 방문
왼쪽 자식 노드를 오른쪽 자식 노드보다 먼저 방문
순회의 결과는 전체 노드를 레벨 0부터 왼쪽에서 오른쪽으로 훑는 것과 같음

넓이 우선 순회의 구현

한 노드를 방문했을 때,
나중에 방문할 노드들을 순서대로 기록해두어야 -> 큐를 이용!
1. 루트를 큐에 넣는다
2. 큐에서 A를 꺼낸다(방문) 그리고 큐에 루트의 자식들을 넣는다(왼쪽 자식 먼저).
3. 큐에서 노드를 꺼낸다. 꺼낸 큐의 자식을 넣는다.
4. 큐가 빌때까지 과정 반복

1. (초기화) traversal <- 빈리스트, q <- 빈 큐
2. 빈트리가 아니면, root node 를 q에 추가
3. q가 비어있지 않는동안
   3.1 node <- q에서 원소를 추출
   3.2 node 를 방문
   3.3 node의 왼쪽, 오른쪽 자식(있으면) 들을 q에 추가
4. q가 빈큐가 되면 모든 노드 방문 완료

이진 탐색 트리

모든 노드에 대해서,

• 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
• 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리
  *중복되는 데이터는 없다고 가정

이진 탐색 트리의 구현

데이터 표현 - 각 노드는 (key, value)의 쌍으로
insert
입력인자 : 키, 데이터 원소
리턴 : 없음