1. 트리 구조란???

트리 구조는 노드들의 집합으로 이루어지며 각 노드는 하나의 부모 노드와 여러 개의 자식 노드를 가질 수 있다. 트리는 여러 형태로 존재할 수 있지만 가장 일반적인 형태는 이진 트리로 각 노드가 최대 두 개의 자식을 가진다.

1. 계층적 구조: 트리의 최상위에 위치한 노드를 루트(root)라고 부르며 루트 노드에서부터 각 자식 노드로 연결되는 구조를 가진다.

2. 연결 구조: 노드들이 부모-자식 관계로 연결되어 있으며 각 노드는 다른 노드와 연결되는 에지(edge)를 가진다.

3. 순환 없음: 트리는 순환이 없는 비순환 그래프의 한 종류로 노드들 사이에 반복적으로 연결되는 경로가 존재하지 않는다.

4. 자식-부모 관계: 각 노드는 자식을 가질 수 있으며 이를 통해 데이터를 계층적으로 분류할 수 있다.

2. 트리 구조의 필요성

1. 계층적 데이터 표현: 트리는 데이터 간의 계층 구조를 표현하기에 적합하다.

2. 효율적인 검색 및 정렬: 틀히 이진 탐색 트리는 데이터를 정렬된 형태로 저장할 수 있어 삽입, 삭제, 탐색 등의 연산을 효육적으로 수행할 수 있다.

이진 탐색 트리
1. 해당 노드의 왼쪽에 있는 모든 자식 노드의 값은 해당 노드의 값보다 작다.
2. 해당 노드의 오른쪽에 있는 모든 자식 노드의 값은 해당 노드의 값보다 크다.

예시)
        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

3. 연산 최적화: 특정 상황에서 데이터에 대한 다양한 연산에 최적화된 트리 구조가 존재한다. 예를 들어 힙(heap) 트리는 우선순위 큐 구현에 사용된다.

3. 트리 순회 방법

3.1 Preorder Traversal (전위 순회)

순서

Root -> Left -> Right

Root를 가장 먼저 방문하기에 Preorder(전위)라고 칭한다.

# python 코드

def preorder(node):
    if node:
        print(node.value)  # 현재 노드를 방문
        preorder(node.left)  # 왼쪽 서브트리 방문
        preorder(node.right)  # 오른쪽 서브트리 방문

예시로 보는 전위 순회 방법

    1
   / \
  2   3
 / \
4   5

1. 루트에서 시작한다.

   • 현재 노드 1을 방문한다. (방문 순서에 1 추가)

2. 왼쪽 자식 노드로 이동한다. (Left(2)로 이동)

   • 현재 노드 2를 방문한다. (방문 순서에 2 추가)

3. 다시 왼쪽 자식 노드로 이동한다. (Left(4)로 이동)

   • 현재 노드 4를 방문한다. (방문 순서에 4 추가)
   • 현재 노드 4는 왼쪽과 오른쪽 자식이 없으므로 이전 노드로 돌아간다. (2로 돌아감)

4. 2로 돌아와서, 2의 오른쪽 자식 노드로 이동한다. (Right(5)로 이동)

   • 현재 노드 5를 방문한다. (방문 순서에 5 추가)
   • 현재 노드 5는 왼쪽과 오른쪽 자식이 없으므로, 이전 노드 1로 돌아간다.

5. 1로 돌아와서, 1의 오른쪽 자식 노드로 이동한다. (Right(3)로 이동)

   • 현재 노드 3을 방문한다. (방문 순서에 3 추가)
   • 현재 노드 3은 왼쪽과 오른쪽 자식이 없으므로 순회가 종료된다.

최종 방문 순서: 1 → 2 → 4 → 5 → 3

언제 사용할까??

1. 트리 구조 복제 및 저장 : 트리를 파일로 저장하고 나중에 다시 복원할 때 전위 순회는 트리의 구조를 일관성있게 기록하기에 적합하다.(후위 순회도 적합하다)

2. 수식 표현 트리: 수학적인 표현을 트리 구조로 나타낼 때 전위 표기법으로 표현된 수식을 파싱하고 평가하는 과정에서 유용하다.

3. 트리 기반 알고리즘 구현: 파일 시스템 탐색 등에서 루트부터 탐색을 시작해야 하는 경우 전위 순회가 사용된다.

3.2 Inorder Traversal (중위 순회)

순서

Left -> Root -> Right

Root를 두번째(중간)에 방문하기에 Inorder라고 칭한다.

# python 코드

def inorder(node):
    if node:
        inorder(node.left)  # 왼쪽 서브트리 방문
        print(node.value)  # 현재 노드를 방문
        inorder(node.right)  # 오른쪽 서브트리 방문

예시로 보는 중위 순회 방법

    1
   / \
  2   3
 / \
4   5

1. 루트에서 시작한다.

   • 현재 노드 1에서 왼쪽 자식 노드 2로 이동한다. (Left(2)로 이동)

2. 왼쪽 자식 노드 2로 이동한다.

   • 현재 노드 2에서 다시 왼쪽 자식 노드 4로 이동한다. (Left(4)로 이동)

3. 현재 노드 4를 방문한다. (방문 순서에 4 추가)

   • 현재 노드 4는 왼쪽과 오른쪽 자식이 없으므로 본인 방문 후 이전 노드 2로 돌아간다.

4. 2로 돌아온다.

   • Left를 방문했으므로 현재 노드 2를 방문한다. (방문 순서에 2 추가)
   • 이후 오른쪽 자식 노드 5로 이동한다. (Right(5)로 이동)

5. 현재 노드 5를 방문한다. (방문 순서에 5 추가)

   • 현재 노드 5는 왼쪽과 오른쪽 자식이 없으므로 이전 노드 1로 돌아간다.

6. 1로 돌아온다.

   • Left를 방문했으므로 현재 노드 1을 방문한다. (방문 순서에 1 추가)
   • 이후 오른쪽 자식 노드 3으로 이동한다. (Right(3)로 이동)

7. 현재 노드 3을 방문한다. (방문 순서에 3 추가)

   • 현재 노드 3은 왼쪽과 오른쪽 자식이 없으므로 순회가 종료된다.

최종 방문 순서: 4 → 2 → 5 → 1 → 3

언제 사용할까???

1. 이진 탐색 트리의 정렬: 중위 순회는 이진 탐색 트리에서 노드들을 정렬하여 출력할 때 사용된다. 트리에서 데이터를 순서대로 나열할 수 있다는 장점이 있다.

2. 수식의 변환 : 수학적인 표현을 트리 구조로 나타낼 때 중위 표기법으로 표현된 수식을 파싱하고 평가하는 과정에서 유용하다.

3.3 Postorder Traversal (후위 순회)

순서

Left -> Right -> Root

Root를 마지막에 방문하기에 Postorder라고 칭한다.

# python 코드

def inorder(node):
    if node:
        inorder(node.left)  # 왼쪽 서브트리 방문
        print(node.value)  # 현재 노드를 방문
        inorder(node.right)  # 오른쪽 서브트리 방문

예시로 보는 후위 순회 방법

    1
   / \
  2   3
 / \
4   5

1. 루트에서 시작한다.

   • 현재 노드 1에서 왼쪽 자식 노드 2로 이동한다. (Left(2)로 이동)

2. 왼쪽 자식 노드 2로 이동한다.

   • 현재 노드 2에서 다시 왼쪽 자식 노드로 이동한다. (Left(4)로 이동)

3. 현재 노드 4를 방문한다. (방문 순서에 4 추가)

   • 현재 노드 4는 왼쪽과 오른쪽 자식이 없으므로 이전 노드 2로 돌아간다.

4. 2로 돌아온다.

   • 이후 오른쪽 자식 노드 5로 이동한다. (Right(5)로 이동)

5. 현재 노드 5를 방문한다. (방문 순서에 5 추가)

   • 현재 노드 5는 왼쪽과 오른쪽 자식이 없으므로 이전 노드 2로 돌아간다.

6. 2로 돌아온다.

   • Left, Right 다 방문했으므로 현재 노드 2를 방문한다. (방문 순서에 2 추가)
   • 이후 이전 노드 1로 돌아간다.

7. 1로 돌아온다.

   • 이후 오른쪽 자식 노드 3으로 이동한다. (Right(3)로 이동)

8. 현재 노드 3을 방문한다. (방문 순서에 3 추가)

   • 현재 노드 3은 왼쪽과 오른쪽 자식이 없으므로 이전 노드 1로 돌아간다.

9. 1로 돌아온다.

   • Left, Right 다 방문했으므로 현재 노드 1을 방문한다. (방문 순서에 1 추가)
   • 순회가 종료된다.

최종 방문 순서: 4 → 5 → 2 → 3 → 1

언제 사용할까???

1. 노드 삭제: 이진 트리에서 모든 노드를 삭제하려면 자식 노드부터 삭제해야 하는데 이때 후위 순회를 사용하면 트리의 구조를 유지하면서 안전하게 모든 노드를 삭제할 수 있다.

2. 디렉토리 및 파일 삭제: 위의 노드 삭제와 유사하게 파일 시스템과 같은 계층적 구조에서 디렉토리나 폴더를 삭제할 때는 하위 파일과 폴더를 먼저 삭제해야 한다.

3. 수식의 계산: 수학적인 표현을 트리 구조로 나타낼 때 후위 표기법으로 표현된 수식을 파싱하고 평가하는 과정에서 유용하다.

정리

아래 트리를 전위, 중위, 후위 순회로 방문해 보세요!!

답은 그래프 하단을 드레그하시면 보입니다!

    1
   / \
  2   3
 / \
4   5
   / \
  6   7