Tree

1. 트리(Tree)란?

하나의 가장 상위 노드인 루트 노드 를 가진다.
루트노드는 0개 이상의 자식 노드를 가지고 있다.
그 자식 노드 또한 0개 이상의 자식 노드를 가지고 있고 이를 반복적으로 정의하고 있다.

2. 이진 트리

이진 트리는 자식 노드가 왼쪽, 오른쪽 두개 뿐인 트리다.
이진 트리에는 항상 루트 노드(최상위 노드)가 있다.

* 선순위 (pre-order) 선회 : 루트>왼쪽>오른쪽 순 노드 방문
  ex) [42,41,10,40,50,45,75]

* 후순위 (post-order) 선회 : 왼쪽>오른쪽>루트 순 노드 방문
  ex) [10,40,41,45,75,50,42]

* 중순위 (in-order) 선회 : 왼쪽>로트>오른쪽 순 노드 방문
  ex) [10,41,40,42,45,50,75]

* 단계 순위(level-order) 선회(우선검색 BFS 라고도 불림) :
  왼쪽 , 오른쪽 깊게 들어가는 대신 각 노드 단계를 방문함
  ex) [42,41,50,10,40,45,75]

3. 이진 검색 트리(BST)

왼쪽,오른쪽 자식이 있지만 왼쪽 자식이 부모보다 작고 오른쪽 자식이 부모보다 크다.
이진 검색 트리 구조를 지닌 이유는 검색,삽입,특정 노드값을 지닌 노드 제거 복잡도가 O이기 때문이다.

ex ) 1(왼쪽 노드) | 2(루트 노드) | 3(오른쪽 노드)