트리

트리(Tree)

- 노드(Node)와 가지(Branch)를 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수 형태

 

노드(Node)

- 트리의 기본 요소

 

근 노드(Root Node)

- 트리의 맨 위에 있는 노드

 

디그리(Degree, 차수)

- 각 노드에서 뻗어 나온 가지의 수

 

단말 노드(Terminal Node)

- 잎 노드(Leaf Node)라고도 함

- 자식이 하나도 없는 노드

- 디그리가 0인 노드

 

이진 트리(binary tree)

- 자식 노드가 최대 두개인 노드들로 구성된 트리

- 정이진트리(full binary tree) : 잎새 노드를 제외한 모든 노드가 자식 노드를 2개 가지는 이진트리

- 완전이진트리(complete binary tree) : 마지막 레벨을 제외한 모든 레벨에서 모든 노드가 자식 노드를 2개 가지는 이진트리

- 균형이진트리(balanced binary tree) : 모든 입새노드의 깊이 차이가 최대 1인 이진트리

 

노드의 깊이(depth)?

- 루트에서 어떤 노드에 도달하기까지 거쳐야 하는 가지의 수

 

이진 트리 운행법

 

 

1. Preorder 운행 : Root -> Left -> Right

- A,B,C

 

2. Inorder 운행 : Left -> Root -> Right

- B,A,C

 

3. Postorder 운행 : Left -> Right -> Root

- B,C,A