트리

트리
-어떤 노드의 레벨이 i이면, 자식노드 레벨은 i+1임
-트리구조에서 간선수 e와 노드수 n 관계: e = n-1


이진트리
-2개이하의 자식노드를 갖는 트리. 즉 0~2개의 자식노드
-n개 노드의 이진트리: n+1개의 nil링크 
-깊이가 k인 2진트리 노드수: k~ 2의k승 -1개
-일반트리와 다르게 왼쪽 오른쪽 서브트리를 구분함

이진트리 종류
1) Full 포화 2진트리
-노드 수: 항상 2의 k승 -1개(k=높이)
-레벨 i(1<=i<=k)에서 가질수 있는 노드 수: 항상 2의 i-1승인 이진트리
-트리높이: 항상 log2(n+1)->루트노드 레벨이 1일때임
-모든 단말노드 높이는 같다
-단말노드 개수: 항상 2의 k-1개. 단말노드가 아닌 노드개수: 2의 k-1승 -1개
-단말노드를 제외한 모든 내부노드는 2개의 자식노드를 갖는다. k-1레벨까지의 모든 노드차수는 2임

2) Complete 완전 2진트리
-포화 이진트리의 단말노드들을 올느쪽으로부터 제거하여 얻어지는 트리.
-포화 full이진트리는 완전complete이진트리에 포함

-노드 개수: 2의 k-1승 <=n<=2의 k승 -10
-레벨 i(1<=i<=k)에서 가질수 있는 노드 수: 최대 2의 i-1승
-트리높이: 항상 log2(n+1) -루트노드 레벨이 1일때임
-모든 단말노드 레벨: k또는 k-1
-단말노드개수: 비단말노드 개수 or 비단말노드개수+1
-모든 노드의 차수: 높이가 k인 완전이진트리에서 루트노드 레벨이 1부터 시작시, k-2레벨까지의 모든 노드차수는 2임

3) Knuth 이진트리
-임의의 모든 노드 차수가 2이하인 트리(노드 차수가 0~2)

4) 엄밀한 이진트리
-모든 노드 차수: 0또는 2
-단말노드개수: 비단말노드개수 +1

5) Skewed 사향 이진트리
-한쪽 방향으로만 뻗은 트리


용어 정리
-노드: 트리를 구성하는 요소. 다른노드로 뻗어진 가지를 포함함
-차수: 파생된 직계 노드의 개수 
-트리의 차수: 각 노드 차수중 가장 큰 값
-레벨= 깊이. 루트의 레벨은 1이고, 아래로 내려갈수록 1씩 증가. 단, 루트레벨이 반드시 1은 아님. 0으로 지정 가능함
-높이: 근노드(트리의 시작정점)에서 가장 큰 레벨