트리

1. 트리의 개념

트리는 계층적인 구조를 가지고 있는 자료를 다룰 때 사용하는 자료구조이다.

ex) 가족의 가계도, 회사의 조직도, 컴퓨터의 디렉토리 구조, 인공지능에서의 결정트리

트리는 한 개 이상의 노드로 이루어진 유한 집합니다.
트리의 용어는 다음과 같다.

node: 트리의 구성요소
root: 부모가 없는 노드
subtree: 하나의 노드와 그 노드들의 자손들로 이루어진 트리
단말 노드: 자식이 없는 노드
비단말 노드: 적어도 하나의 자식을 가지는 노드

간선: 루트와 서브트리를 연결하는 선
부모 노드: 자식 노드를 직접 연결하여 위쪽에 위치한 노드
자식 노드: 부모 노드로부터 직접 연결된 하위 노드
형제 노드: 부모가 같은 노드
조상 노드: 루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드들
후손(자손) 노드: 임의의 노드 하위에 연결된 모든 노드들
레벨: 트리의 각층의 번호
높이: 트리의 최대 레벨
차수: 노드가 가지고 있는 자식 노드의 개수

다음은 예제이다.

A는 루트노드이다.
B는 D와 E의 부모노드이다.
C는 B의 형제 노드이다.
D와 E는 B의 자식노드이다.
B의 차수는 2이다.
위의 트리의 높이는 4이다.

---

2. 이진 트리(binary tree)

트리는 여러 종류가 있는데, 여기서는 이진 트리만 다룬다.

이진트리(binary tree): 모든 노드가 2개의 서브 트리를 가지고 있는 트리

이진트리의 노드에는 최대 2개의 자식노드가 존재하고, 모든 노드의 차수가 2 이하이다.
이진트리에는 서브 트리 간의 순서가 존재하고, 공집합인 서브트리가 존재할 수 있다.

1. 이진트리의 성질

• 노드의 개수가 n개이면, 간선의 개수는 n-1개

• 높이가 h인 이진트리의 경우, 최소 노드 h개, 최대 노드 $2^h-1$개
  레벨 i에서의 노드의 최대개수는 $2^{i-1}$
  

• n개의 노드를 가지는 이진트리의 높이는 최대 n, 최소 $\log_2(n+1)$
  

2. 이진트리의 분류
   다음과 같은 3개의 이진트리가 있다.

   포화 이진 트리(full binary tree)
   
   완전 이진 트리(complete binary tree)
   
   기타 이진 트리
   

3. 포화 이진 트리(full binary tree): 트리의 각 레벨에 노드가 꽉 차 있는 이진트리
   • 높이 k인 포화 이진트리는 정확히 $2^k-1$개의 노드를 가진다.
   • 레벨 단위로 왼쪽에서 오른쪽으로 노드의 번호를 붙이면 됨
     - 따라서 루트 노드의 오른쪽 자식 노드의 번호는 항상 3임
     

4. 완전 이진 트리(complete binary tree): 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고, 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져있는 이진트리
   • 포화 이진트리와 노드 번호가 일치
     

---

3. 이진트리의 표현

이진트리는 2가지 방법(배열과 포인터)를 이용해 표현할 수 있다.

1. 배열 표현법
   모든 이진트리를 포화 이진트리라 가정하고 각 노드에 번호를 붙여 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장한다.
   번호를 붙인 순서대로 배열에 저장하면 되는데, 이때 인덱스 0은 사용하지 않는다.

인덱스를 통해 쉽게 부모와 자식 노드를 찾을 수 있다.

노드 i의 부모 노드 인덱스: i/2
노드 i의 왼쪽 자식 노드 인덱스: 2i
노드 i의 오른쪽 자식 노드 인덱스: 2i + 1

2. 링크 표현법
   포인터를 이용하여 부모노드가 자식노드를 가리키게 하는 방법이다.
   하나의 노드는 총 3개의 포인터 데이터 필드, 왼쪽과 오른쪽 자식 노드를 가리키는 포인터 필드를 가진다.
   

이진트리의 노드는 구조체로, 링크는 포인터로 표현한다.

typedef struct TreeNode{
	int data;
    struct TreeNode *left, *right;
} TreeNode;

링크법으로 생성된 이진트리는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct TreeNode{
	int data;
    struct TreeNode *left, *right;
} TreeNode;
//       n1
//      / |
//     n2 n3
int main(void)
{
	TreeNode *n1, *n2, *n3;
    n1 = (TreeNode *)malloc(sizeof(TreeNode));
    n2 = (TreeNode *)malloc(sizeof(TreeNode));
    n3 = (TreeNode *)malloc(sizeof(TreeNode));
    n1->data = 10; // 첫번째 노드를 설정함
    n1->left = n2;
    n1->right = n3;
    n2->data = 20; // 두번째 노드를 설정함
    n2->left = NULL;
    n2->right = NULL;
    n3->data = 30; // 세번째 노드를 설정함
    n3 >left = NULL;
    n3->right = NULL;
    free(n1); free(n2); free(n3); 
    return 0;
}