[C++로 배우는 알고리즘과 자료구조] Day 6: 트리의 기본 개념

트리 (Tree)

트리는 계층적 자료구조로, 노드(Node)와 간선(Edge)으로 구성됩니다. 트리는 하나의 루트(Root) 노드를 가지며, 각 노드는 자식 노드를 가질 수 있습니다. 트리는 사이클이 없는 비순환 그래프입니다.

트리의 용어:

1. 루트 노드 (Root Node): 트리의 최상위 노드입니다.
2. 부모 노드 (Parent Node): 특정 노드의 바로 위에 있는 노드입니다.
3. 자식 노드 (Child Node): 특정 노드의 바로 아래에 있는 노드입니다.
4. 리프 노드 (Leaf Node): 자식 노드가 없는 노드입니다.
5. 서브트리 (Subtree): 노드와 그 자손 노드들로 이루어진 트리의 부분 집합입니다.
6. 높이 (Height): 루트 노드에서 리프 노드까지의 최대 경로 길이입니다.

이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 이진 트리는 여러 가지 형태로 변형될 수 있으며, 이진 탐색 트리(BST), AVL 트리, 힙 등이 있습니다.

이진 트리의 종류:

1. 포화 이진 트리 (Full Binary Tree): 모든 노드가 두 개의 자식 노드를 가지거나 자식 노드가 없는 트리입니다.
2. 완전 이진 트리 (Complete Binary Tree): 마지막 레벨을 제외하고 모든 레벨이 완전히 채워진 트리입니다.
3. 이진 탐색 트리 (Binary Search Tree, BST): 왼쪽 서브트리의 모든 값은 루트의 값보다 작고, 오른쪽 서브트리의 모든 값은 루트의 값보다 큰 트리입니다.

이진 트리 구현 예제

BinaryTree.h

#ifndef BINARYTREE_H
#define BINARYTREE_H

#include <iostream>

// 이진 트리의 노드 구조체
struct TreeNode {
    int data; // 데이터
    TreeNode* left; // 왼쪽 자식 노드를 가리키는 포인터
    TreeNode* right; // 오른쪽 자식 노드를 가리키는 포인터

    TreeNode(int value) : data(value), left(nullptr), right(nullptr) {} // 노드 생성자
};

// 이진 트리 클래스
class BinaryTree {
public:
    BinaryTree() : root(nullptr) {} // 생성자
    ~BinaryTree(); // 소멸자

    void insert(int value); // 값 삽입
    void inOrderTraversal() const; // 중위 순회
    void preOrderTraversal() const; // 전위 순회
    void postOrderTraversal() const; // 후위 순회

private:
    TreeNode* root; // 트리의 루트 노드를 가리키는 포인터

    void insert(TreeNode*& node, int value); // 값 삽입 (재귀)
    void inOrderTraversal(TreeNode* node) const; // 중위 순회 (재귀)
    void preOrderTraversal(TreeNode* node) const; // 전위 순회 (재귀)
    void postOrderTraversal(TreeNode* node) const; // 후위 순회 (재귀)
    void destroy(TreeNode* node); // 트리 파괴 (재귀)
};

// 소멸자 정의 (메모리 해제)
BinaryTree::~BinaryTree() {
    destroy(root);
}

// 트리 파괴 함수 정의 (재귀)
void BinaryTree::destroy(TreeNode* node) {
    if (node != nullptr) {
        destroy(node->left);
        destroy(node->right);
        delete node; // 노드 메모리 해제
    }
}

// 값 삽입 함수 정의 (재귀)
void BinaryTree::insert(TreeNode*& node, int value) {
    if (node == nullptr) {
        node = new TreeNode(value); // 새로운 노드 생성
    } else if (value < node->data) {
        insert(node->left, value); // 왼쪽 서브트리에 삽입
    } else {
        insert(node->right, value); // 오른쪽 서브트리에 삽입
    }
}

// 값 삽입 함수 정의
void BinaryTree::insert(int value) {
    insert(root, value);
}

// 중위 순회 함수 정의 (재귀)
void BinaryTree::inOrderTraversal(TreeNode* node) const {
    if (node != nullptr) {
        inOrderTraversal(node->left);
        std::cout << node->data << " ";
        inOrderTraversal(node->right);
    }
}

// 중위 순회 함수 정의
void BinaryTree::inOrderTraversal() const {
    inOrderTraversal(root);
    std::cout << std::endl;
}

// 전위 순회 함수 정의 (재귀)
void BinaryTree::preOrderTraversal(TreeNode* node) const {
    if (node != nullptr) {
        std::cout << node->data << " ";
        preOrderTraversal(node->left);
        preOrderTraversal(node->right);
    }
}

// 전위 순회 함수 정의
void BinaryTree::preOrderTraversal() const {
    preOrderTraversal(root);
    std::cout << std::endl;
}

// 후위 순회 함수 정의 (재귀)
void BinaryTree::postOrderTraversal(TreeNode* node) const {
    if (node != nullptr) {
        postOrderTraversal(node->left);
        postOrderTraversal(node->right);
        std::cout << node->data << " ";
    }
}

// 후위 순회 함수 정의
void BinaryTree::postOrderTraversal() const {
    postOrderTraversal(root);
    std::cout << std::endl;
}

#endif // BINARYTREE_H

 

이진 트리 예제

#include <iostream>
#include "BinaryTree.h"

int main() {
    BinaryTree tree;
    tree.insert(5);
    tree.insert(3);
    tree.insert(7);
    tree.insert(2);
    tree.insert(4);
    tree.insert(6);
    tree.insert(8);

    std::cout << "중위 순회: ";
    tree.inOrderTraversal(); // 중위 순회 출력

    std::cout << "전위 순회: ";
    tree.preOrderTraversal(); // 전위 순회 출력

    std::cout << "후위 순회: ";
    tree.postOrderTraversal(); // 후위 순회 출력

    return 0;
}

 

설명

1. 이진 트리 (Binary Tree):
   • 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.
   • 각 노드는 데이터를 저장하고, 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키는 포인터를 가집니다.
2. 트리 순회:
   • 중위 순회 (In-order Traversal): 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 방문합니다.
   • 전위 순회 (Pre-order Traversal): 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 방문합니다.
   • 후위 순회 (Post-order Traversal): 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순서로 방문합니다.
3. 트리의 주요 연산:
   • 삽입 (Insert): 트리에 새로운 값을 삽입합니다.
   • 순회 (Traversal): 트리의 모든 노드를 특정 순서로 방문합니다.
   • 파괴 (Destroy): 트리의 모든 노드를 메모리에서 해제합니다.

이제 트리의 기본 개념과 이진 트리의 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 자료구조와 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 7: 이진 탐색 트리 (BST)"에 대해 학습하겠습니다.