트리(Tree), 이진트리(Binary Tree)

트리(Tree)

트리는 1개 이상의 노드로 이루어진 유한집합으로서,

1) 노드 중에는 루트(root)라는 노드가 하나 있고,

2) 나머지 노드들은 n(>=0)개의 분리 집합 T1,T2, ... , Tn으로 분할될 수 있다.

차수(Degree): 한 노드의 서브트리의 수

- Leaf/Terminal Node: 차수가 0인 노드

- Sibling Node: 같은 부모노드를 가진 노드들

- Degree of a tree: 트리에 있는 노드의 최대 차수

- Ancestor: 루트에서부터 그 노드까지 경로상의 모든 노드

위의 그림의 예시로 들어보겠다.

1) Leaf/Terminal Nodes: K, L, F, G, M, I, J

2) Sibling Nodes: (K & L) , (F & G & H), (B & C & D) 등

3) Degree of the tree: 3 (C의 차수가 최대인 3이다)

4) M의 Ancestor: H, C, A

이진트리(Binary Tree)

이진트리는 공백이거나 루트와 왼쪽 서브트리, 오른쪽 서브트리라고 하는 2개의 분리된 이진트리로 구성된 노드의 유한집합이다.

이진트리는 일반적인 트리와의 차이점을 비교하는 것으로 설명하도록 하겠다.

일반 트리(Normal Tree)	이진 트리(Binary Tree)
- 0개의 노드를 가진 트리는 없다. - 자식의 순서를 구분하지 않는다        - <그림1>과 <그림2>는 같다	- 0개의 노드를 가진 트리가 있다. - 자식의 순서를 구분한다.        - <그림1>과 <그림2>는 각각           오른쪽과 왼쪽 노드를 자식으로           가진 다른 트리이다

이진트리의 성질

1) 이진트리의 레벨 i에서의 최대 노드의 수는 2^(i-1)  (i>=1)이다.

2) 깊이가 k인 이진트리의 최대 노드 수는 2^k - 1    (k>=1)이다.

3) 공백이 아닌 모든 이진트리에서 리프 노드 수 = 차수가 2인 노드의 수 + 1 이다.