tree

/*
* 트리 자료형과 그래프 자료형
* 
* 그래프 자료형 - 연결관계를 표현할수 있다면 그래프 자료형이다.
* 그래프 자료형 속에 트리가 포함돼있다고 볼 수 있다.
* 그래프 안에 연결관계에서 처음 시작 노드에서 한바퀴를 돌아서 처음 시작 노드로 돌아올 수 있으면 순회가 가능하다고 본다.
* 트리는 순회가 불가능한 그래프입니다.
* 트리는 주로 언제 쓰는가 -> 계층관계를 표현할때 유용하다.(조직도)
* 대표적인 트리구조가 윈도우의 폴더구조이다.
* 
* 트리용어 - level(높이) 0 ~ 0+n  루트 <-0-----0+n-> 리프  -  0에 가까울수록 루트에 가깝다.
* 루트노드 - 부모가 없는 노드.
* 리프(단말)노드 - 자식이 없는 노드.
* 
* 이진트리 - 이런 트리중에서도 자식을 가질수있는 갯수를 2개로 제한한 트리를 이진트리라고 부른다.
* 완전이진트리 - 루트노드로 시작해서 자식을 항상 꽉꽉 채워나가는 형태의 이진트리.
* 
* 완전이진트리는 일반적으로 배열로 구현한다.
* 완전이진트리만의 배열 접근법.
*  (부모->자식)
* n번 노드의 첫번째 자식은 n번 노드의 인덱스 = k -> 2k+1 
* n번 노드의 두번째 자식은 n번 노드의 인덱스 = k -> 2k+2
*
* (자식->부모) 
* (인덱스-1 / 2)의 몫 인덱스가 부모노드.
* 완전이진트리는 힙이라는 자료구조를 만들때 쓰이게 된다. (스스로 공부)
* 
* 이진탐색트리 - 탐색을 위한 이진트리 - 이진(Binary)탐색(Search)트리(Tree) - 이진탐색이 중요.
* 이진탐색이란 무엇일까?
* 1. 기본조건 - 데이터가 정렬되어있어야 된다.
* 2. 문제를 절반으로 줄여나가면서 탐색하는 방법이다. \log_2{n} -> O(logN)      -> \log_10{1000} - 10의 몇승이 1000이 되냐? 10^x = 1000 -> x = 3
* 
* 순회 규칙
* 전위순회 부모 -> 왼쪽 -> 오른쪽
* 중위순회 왼쪽 -> 부모 -> 오른쪽
* 후위순회 왼쪽 -> 오른쪽 -> 부모
* 
* 이진탐색트리의 문제점.
* 데이터의 입력이 순차적으로 될 때.
*/