트리 정의

트리는 계층적 관계를 표현하는 자료구조이며, 트리를 구성하는 요소는 노드(node)와 가지(edge)입니다.
각각의 노드는 가지를 통해 다른노드와 연결되어 있습니다.

• 루트: 트리의 가장 윗부분에 위치하는 노드를 루트(root)라고 합니다. 하나의 트리에는 하나의 루트가 있습니다.
• 리프: 트리의 가장 아랫부분에 위치하는 노드를 리프(leaf)라고 합니다. 더 이상 뻗어나갈 수 없는 마지막 노드를 말합니다.
• 안쪽 노드: 루투를 포함하여 리프을 제외한 노드를 안쪽 노드라고 합니다.
• 자식: 어떤 노드로부터 가지로 연결된 아래쪽 노드를 자식(child)이라고 합니다.
• 부모: 어떤 노드에서 가지로 연결된 위쪽 노드를 부모라고 합니다.
• 형제: 같은 부모를 가지는 노드를 형제라고 합니다.
• 조상: 어떤 노드에서 가지로 연결된 위쪽 노드 모두를 조상이라고 합니다.
• 자손: 어떤 노드에서 가지로 연결된 아래쪽 노드 모두를 자손이라고 합니다.
• 레벨: 루트로부터 얼마나 떨어져 있는지에 대한 값을 레벨이라고 합니다.
• 차수: 노드가 갖는 자식의 수를 차수라고 합니다.
• 높이: 루트로부터 가장 멀리 떨어진 리프까지의 거리를 높이라고 합니다.
• 서브 트리: 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리를 서브 트리라고 합니다.
• 널 트리: 노드, 가지가 없는 트리를 널 트리라고 합니다.
  
  

트리 특징

• 그래프의 한 종류이다. ‘최소 연결 트리’ 라고도 불린다.
• 트리는 계층 모델 이다.
• 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.
  • loop나 circuit이 없다. 당연히 self-loop도 없다.
  • 즉, 사이클이 없다.
• 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
  • 즉, 간선은 항상 (정점의 개수 - 1) 만큼을 가진다.
• 루트에서 어떤 노드로 가는 경로는 유일하다.
  • 임의의 두 노드 간의 경로도 유일하다. 즉, 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
• 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
  • 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.
• 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS 안에 있다.
• 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.
  

트리 종류

• 완전이진트리(complete binary tree): 루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리를 완전이진트리라고 합니다.
• 포화이진트리(Full binary tree): 모든 잎의 레벨이 동일한 이진 트리이며, 잎이 아닌 내부 노드들은 모두 2개의 자식을 가지는 트리 입니다. 포화이진트리는 완전이진트리라고도 불립니다.
  
  

참조

• 강아지의 코딩공부
• HeeJeong Kwon Blog
• 자료구조와 함께 배우는 알고리즘 입문 (자바 편)
• 윤성우의 열혈 C 자료구조