[자료구조] 트리 (이진트리, 순회 알고리즘)

트리는 나뭇가지처럼 노드들이 연결된 비선형적고 계층적인 자료구조이다. (재귀적 : 트리 내 또 다른 트리)

사이클이 아닌 비순환 자료구조이므로,

부모 노드와 자식 노드의 관계로 노드들이 연결되며 트리 구조를 이루게 된다.

 

나무를 거꾸로 매단 것 같은 구조여서 '트리'라는 이름이 붙었다.

대표적인 예시로는 컴퓨터의 디렉토리라고 할 수 있다.

Directory

 

트리 구조 

 

루트 노드(root node): 

부모가 없는 노드

트리는 하나의 루트 노드만을 가진다.

• 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음.
• 노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가짐.

단말 노드(leaf node): 

자식이 없는 노드 (‘말단(terminal)노드’ 또는 ‘잎 노드’라고도 부름)

Breadth : leaf node의 수

내부(internal) 노드: 

단말 노드가 아닌 노드 = 자식 노드 하나 이

간선(edge): 

노드를 연결하는 선 (link, branch 라고도 부름)

Distance : 두 노드 사이의 최단 경로에 있는 간선(Edge)의 수

형제(sibling): 

같은 부모를 가지는 노드

노드 크기(size): 

자신을 포함한 모든 자손 노드의 개수

노드 깊이(depth): 

루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

노드 레벨(level): 

트리의 특정 깊이를 가지는 노드의 집합

노드 차수(degree): 

하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수

트리 차수(degree of tree): 

트리의 최대 차수

트리 높이(height): 

루트 노드에서 가장 깊숙히 있는 노드의 깊이

Order

부모 노드가 가질 수 있는 최대 자식의 수

ex) Order 3 : 부모 노드는 최대 3명의 자식을 가질 수 있다.

---

트리의 순회 방법

• 전위 순회 (Preorder) - root > 왼쪽 > 오른쪽

      A
     / \
    B   C
   / \
  D   E

순서: A → B → D → E → C

 

루트부터 방문하고 왼쪽 - 오른쪽 순서로 방문한다.

 

• 중위 순회 (Inorder) - 왼쪽 > root > 오른쪽

      A
     / \
    B   C
   / \
  D   E

순서: D → B → E → A → C

 

왼쪽 서브트리를 모두 탐색한 뒤 root을 방문하고 그 다음에 오른쪽 서브트리를 탐색한다.

이진 탐색 트리에서는 중위 순회 결과가 정렬된 순서가 된다.

 

• 후위 순회 (Postorder) - 왼쪽 > 오른쪽 > root

      A
     / \
    B   C
   / \
  D   E

순서: D → E → B → C → A

 

자식 노드들을 먼저 다 돌고, root를 나중에 방문하는 방식이다.

---

이진트리와 완전 이진 트리

• 이진 트리 (Binary Tree)

      A
     / \
    B   C
       /
      D

 

이진 트리란, 한 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리이다.

자식 노드는 꼭 왼쪽부터 채울 필요는 없다.

 

• 완전 이진 트리 (Complete Binary Tree)

      A
     / \
    B   C
   / \
  D   E

 

왼쪽부터 빈틈 없이 채워진 트리이다.

마지막 레벨은 왼쪽부터 차례대로 채워져 있어야 완전 이진 트리라고 할 수 있다.

C의 오른쪽 지식은 없더라도, D와 E는 반드시 왼쪽부터 채워져 있어야 한다는 뜻!

---

이진 탐색 트리 (Binary Search Tree)

       8
     /   \
    3     10
   / \      \
  1   6      14
     / \     /
    4   7   13

 

각 노드는 왼쪽에는 자기보다 작은 값, 오른쪽에는 자기보다 큰 값을 가진다.

 

탐색(Search):

예를 들어 4를 찾고 싶다면
→ 8보다 작으니까 왼쪽 3
→ 3보다 크니까 오른쪽 6
→ 6보다 작으니까 왼쪽 4 → 찾음

 

하지만 정렬된 데이터를 순서대로 삽입하면 한쪽으로 쏠린 비효율적 트리가 되므로,

균형 이진 트리(AVL, Red-Black) 등을 사용하는 경우도 많다.

---

순회 알고리즘 구현

트리 노드 구조체

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

typedef struct TreeNode {
    char data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

 

• 전위 순회 알고리즘

void preorder(TreeNode* root) {
    if (root == NULL) return;
    printf("%c ", root->data);
    preorder(root->left);
    preorder(root->right);
}

 

• 중위 순회 알고리즘

void inorder(TreeNode* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%c ", root->data);
    inorder(root->right);
}

 

• 후위 순회 알고리즘

void postorder(TreeNode* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%c ", root->data);
}

 

위 코드들을 바탕으로 트리를 한 번 생성해보자.

TreeNode* createNode(char data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    TreeNode* root = createNode('A');
    root->left = createNode('B');
    root->right = createNode('C');
    root->left->left = createNode('D');
    root->left->right = createNode('E');

    printf("Preorder: ");
    preorder(root);
    printf("\n");

    printf("Inorder: ");
    inorder(root);
    printf("\n");

    printf("Postorder: ");
    postorder(root);
    printf("\n");

    return 0;
}

         A
      /      \
     B      C
    /  \ 
  D   E

Preorder: A B D E C
Inorder: D B E A C
Postorder: D E B C A