트리
트리는 다음과 같은 하나 이상의 노드의 유한 집합이다.
1) 루트라 불리는 특별히 지정된 노드가 있다.
2) 나머지 노드는 n>=0 disjoint set T1,...,Tn으로 분할한다. 여기서 각각의 노드는 트리이고, T1,...,Tn은 루트의 하위 트리라고 불린다.
- 노드(node) : 한 정보 아이템에 다른 노드로 뻗어진 가지를 합친 것을 의미한다.
- 차수(degree) : 한 노드의 서브트리의 수
- 리프 (leaf) : 차수가 0인 노드 , 단말 노드(terminal node)라고도 한다.
- 현 노드위 상위 노드를 부모(parent)라 하고 부모 하위 노드를 자식(child)이라고 하며 이웃한 노드를 자매(sibilings) 노드라고 한다.
- 현 노드위 상위 노드를 부모(parent)라 하고 부모 하위 노드를 자식(child)이라고 하며 이웃한 노드를 자매(sibilings) 노드라고 한다.
- 트리의 차수(degree of a tree) : 그 트리에 있는 노드의 최대 차수
- 레벨(level) : 루트의 레벨을 1로 정한 뒤에 정의된다. 한 노드의 레벨이 l이면 그 자식의 레벨은 l+1이 된다.
- 레벨(level) : 루트의 레벨을 1로 정한 뒤에 정의된다. 한 노드의 레벨이 l이면 그 자식의 레벨은 l+1이 된다.
- 높이(height) : 그 트리에 속한 노드의 최대 레벨
이진 트리 (binary tree)
이진 트리는 유한한 노드 집합으로, 비어 있거나 루트로 구성되며,
왼쪽 하위 트리와 오른쪽 하위 트리라고 하는 두개의 분리된 이진 트리로 구성된다.
[최대 노드 수]
1. 이진 트리의 레벨 i에서의 최대 노드 수는
2. 깊이가 k인 이진 트리의 최대 노드 수는 
이진 트리는 포화 이진 트리(full binary tree) 와 완전 이진 트리Complete Binary Tree) 가 있다.
-포화 이진 트리(full binary tree) : 깊이가 k이고 노드 수가
인 이진 트리
인 이진 트리-완전 이진 트리(Complete binary tree) : 깊이가 k이고 노드 수가 n인 이진 트리의 각 노드들이 깊이 k인 포화 이진 트리에서 1부터 n까지의 버놓를 붙인 노드들과 1대 1로 일치한다면, 이 트리는 오나전 이진 트리이다.
이 두 트리는 배열로도 표현 가능하다.
부모는 [i/2] 왼쪽 자식은 2*i 오른쪽 자식은 2*i+1 로 표현
이진 트리는 또한 링크드리스트(Linked list)로도 표현 가능하다.
typedef struct node *treePointer;
typedef struct node{
int data;
treePointer leftChild, rightChild;
};
