[자료 구조] Tree & Binary Tree의 개념 설명

⬛ Tree의 개념

• 원소들 간에 1 : n 관계, 계층 관계를 가지는 자료 구조
• 노드(Node)와 간선(Edge)으로 이루어진 자료구조
• 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료 구조
• Loop를 갖지 않는다.

⬛ Tree의 용어

해당 트리의 차수는 2이며, 트리의 깊이는 3이다. 루트 노드의 깊이는 0이며, 높이는 3이다.

• 노드(Node) : 트리의 기본 원소
• 간선(Edge) : 노드와 노드를 연결하는 선, 부모 노드와 자식 노드는 간선으로 연결되어 있다.
• 루트 노드(Root Node) : 트리의 시작 노드로 부모 노드가 없는 최상위 노드
• 부모 노드(Parent Node) : 자식 노드를 가진 노드
• 자식 노드(Child Node) : 부모 노드의 하위 노드
• 형제 노드(Sibling Node) : 같은 부모를 가지는 자식 노드들
• 서브 트리(Sub-tree) : 부모 노드와의 연결을 끊었을 때 임의의 하나의 노드가 루트가 되는 부속 트리
• 조상 노드(Ancestor Node) : 한 노드에서 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
• 자손 노드(Decendant Node) : 한 노드에서 간선을 따라 리프 노드까지 이르는 경로에 있는 모든 노드들
• 단말 노드(Leaf Node) : 자식 노드가 없는 노드
• 차수 (Degree)
  1. 노드의 차수 : 노드에 연결된 자식 노드의 수
  2. 트리의 차수 : 트리에 있는 노드의 차수 중 가장 큰 값
• 레벨 (Level) = Depth
  1. 노드의 레벨 : 루트 노드에서 노드에 이르는 간선의 수
  2. 트리의 레벨 : 트리에 있는 노드 레벨 중에서 가장 큰 값
• 높이(Height) : 어떤 노드에서 단말 노드까지 이르는 가장 긴 경로의 간선의 수 → 단말 노드의 높이는 0이며, 루트 노드의 높이는 트리의 레벨과 같다.

⬛ Binary Tree의 개념

• 자식 노드의 개수가 최대 2개까지만 가질 수 있는 트리
• 왼쪽 서브 트리와 오른쪽 서브 트리로 구성되어 있는 트리이며 서브 트리는 공집합일 수 있다.
• N개의 노드를 가진 이진 트리는 N-1개의 간선을 가진다.
• 레벨 i에서 가질 수 있는 노드의 최대 개수는 (2 ^i)개이다.
• 레벨이 i인 이진 트리의 경우, 최소 (i+1)개의 노드를 가질 수 있고, 최대 (2^(i+1) - 1)개를 가질 수 있다.

⬛ Binary Tree의 종류

1. 포화 이진 트리 : 최대 개수의 노드를 가지는 트리 (레벨이 i일때 (2^(i+1) - 1)개의 노드를 가진 트리)
2. 완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 각 레벨에 대해 (2^i)개의 노드로 채워져 있고 마지막 레벨의 노드는 가능한한 왼쪽으로 채워져 있는 트리
3. 편향 이진 트리 : 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드들만 가지는 트리 (레벨이 i일때 (2+i)개의 노드를 가지며 한쪽 방향의 자식 노드들만 가지는 트리)

⬛ Binary Tree의 표현

• 인덱스를 이용하여 트리를 표현하기 위해 인덱스 0은 사용하지 않음
• 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
• 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
• 부모 노드의 인덱스 = 자식 노드의 인덱스 / 2

⬛ Binary Tree의 순회

1. 전위 순회 : 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순으로 방문
   • A → B → C → D → E → F → G
2. 중위 순회 : 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순으로 방문
   • D → B → E → A → F → C → G
3. 후위 순회 : 왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드 순으로 방문
   • D → E → B → F → G → C → A