[알고리즘] 트리

트리
-비선형구조
-상위 원소와 하위 원소로 이루어진 트리(나무) 모양의 구조
-1:N 관계를 가진다.
- 최상위 노드를 루트라고 한다.
-가장 마지막에 존재하는 루트를 단말노드(잎노드)라고 한다.

차수 : 노드에 연결된 자식 노드의 수
높이 : 루트노드에서 노드까지의 간선의 수

이진트리 : 모든 노드들이 최대 2개의 서브트리를 갖는 트리. 방향에 따라 왼쪽 자식노드/오른쪽 자식노드라고 부른다. 높이가 h이면 가질 수 있는 노드의 최소 개수는 h+1개 이며 최대 개수는 2^h+1 -1 개
특별한 이진트리
- 포화 이진트리 :
모든 노드에 포화 상태로 차 있는 이진 트리
자식 노드가 모두다 2개씩 있는 것이다.(마지막 레벨까지 꽉 참)
-완전 이진 트리:
포화 이진 트리의 노드번호를 따라서 1번부터 n번까지 빈자리가 없는 이진 트리. 마지막 레벨까지 꽉 차지 않아도 되고 순서대로 빈자리가 있으면 안된다.
-편향 이진 트리:
한쪽 방향의 자식 노드만을 가진 이진트리(선형자료구조와 마찬가지)

트리를 방문하는 방법 => 순회
1. 전위순회(부모 먼저)  : 부모노드 -  왼자식-오른자식 순으로 순회 VLR
2. 중위순회(중간에 부모) : 왼자식-부모-오른자식 순
LVR
3. 후위순회(마지막에 부모) : 왼자식-오른자식-부모노드 LRV