자료구조 - 트리

[트리]

지금까지 리스트, 스택, 큐 등은 선형 자료 구조(linear data structure)를 알아보았습니다.

이번에 알아보는 트리는 계층적인 구조(hierarchical structure)입니다.

 

트리의 용어

루트 노드 (Root Node): 트리의 최상위 노드로, 부모 노드가 없습니다.
부모 노드 (Parent Node): 자식 노드를 가지는 노드입니다.
자식 노드 (Child Node): 부모 노드로부터 연결된 노드입니다.
형제 노드 (Sibling Nodes): 동일한 부모를 가지는 노드들입니다.
단말 노드, 리프 노드 (Leaf Node): 자식 노드가 없는 노드입니다.
깊이 (Depth): 루트 노드로부터 특정 노드까지의 경로 길이입니다.
높이 (Height): 특정 노드로부터 가장 깊은 리프 노드까지의 경로 길이입니다.
서브트리 (Subtree): 트리의 특정 노드와 그 자식 노드들로 구성된 부분 트리입니다.

 

 

 

 

[이진 트리]

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.

자식 노드는 왼쪽 자식 (left child)과 오른쪽 자식 (right child)으로 구분됩니다.

 

 

 

이진 트리의 성질

 

● 이진 트리의 최대 노드 수: 레벨 i에서 최대 노드 수는 2ⁱ개입니다.
● 높이가 h인 이진 트리의 최대 노드 수는 2^h+1 - 1개입니다.
● 높이가 h인 이진 트리의 최소 노드 수는 h + 1개입니다.

 

 

이진 트리의 분류

• 포화 이진 트리 (Full Binary Tree): 모든 레벨에서 노드가 꽉 차 있는 트리입니다.
• 완전 이진 트리 (Complete Binary Tree): 마지막 레벨을 제외하고 모든 레벨이 채워져 있으며, 마지막 레벨의 노드들은 왼쪽부터 채워져 있는 트리입니다.

 

 

 

[이진 트리의 표현 방법]

 

1. 배열로 이진트리 표현

배열로 이진트리를 표현하는 방법은 저장하고자 하는 트리를 완전 이진 트리라고 가정하고, 트리의 깊이가 n 이면 2ⁿ- 1개의 공간을 연속적으로 할당한 다음, 완전 이진 트리의 번호대로 노드를 저장합니다.

 

아래의 그림과 같이 표현이 가능하지만 인덱스 0 은 사용하지 않는 점을 주의해야하고, 완전 이진 트리가 아닌 경우 메모리 낭비가 심합니다. 

 

 

 

 

배열로 구현한 이진트리

#include <iostream>
using namespace std;

class BinaryTree
{
    public:
        int* tree;
        int size;

        BinaryTree(int capacity) 
        {
            tree = new int[capacity];
            size = capacity;
            for (int i = 0; i < capacity; ++i)
            {
                tree[i] = -1;  // -1을 사용하여 빈 노드를 표시
            }
        }

        void setRoot(int key)
        {
            tree[0] = key;
        }

        void setLeftChild(int parentIndex, int key) 
        {
            int leftChildIndex = 2 * parentIndex + 1;
            if (leftChildIndex < size)
            {
                tree[leftChildIndex] = key;
            }
        }

        void setRightChild(int parentIndex, int key) 
        {
            int rightChildIndex = 2 * parentIndex + 2;
            if (rightChildIndex < size) 
            {
                tree[rightChildIndex] = key;
            }
        }

        void display() 
        {
            for (int i = 0; i < size; ++i) 
            {
                if (tree[i] != -1) 
                {
                    cout << tree[i] << " ";
                } 
                else
                {
                    cout << "- ";
                }
            }
            cout << endl;
        }
        
        ~BinaryTree() 
        {
            delete[] tree;
        }
};

int main() 
{
    BinaryTree bt(7);  // 크기 7인 이진 트리 생성
    bt.setRoot(1);
    bt.setLeftChild(0, 2);
    bt.setRightChild(0, 3);
    bt.setLeftChild(1, 4);
    bt.setRightChild(1, 5);
    bt.setLeftChild(2, 6);
    bt.display();  // 출력: 1 2 3 4 5 6 -
    return 0;
}

 

 

 

 

2. 포인터로 이진 트리 표현 

 

 

링크 표현법

링크 표현법에서는 트리의 노드가 구조체로 표현되고, 각 노드가 포인터를 가지고 있어서 포인터를 이용하여 노드와 노드를 연결하는 방법입니다.

아래 그림과 같이 하나의 노드가 3개의 필드를 가지는데 데이터 저장하는 필드와 2개의 포인터 필드를 가집니다.

 

이진트리 표현법으로 트리를 표현하면 다음과 같습니다.

 

 

 

 

포인터로 구현한 이진 트리

#include <iostream>
using namespace std;
    
// 노드 구조 정의
struct TreeNode 
{
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val)
    {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

// 이진 트리 클래스 정의
class BinaryTree 
{
    public:
        TreeNode* root;

        BinaryTree() 
        {
            root = nullptr;
        }
    
        void insert(int value) 
        {
            if (root == nullptr) 
            {
                root = new TreeNode(value);
            } 
            else 
            {
                insertHelper(root, value);
            }
        }

        void insertHelper(TreeNode* node, int value) 
        {
            if (value < node->data) 
            {
                if (node->left == nullptr) 
                {
                    node->left = new TreeNode(value);
                } 
                else 
                {
                    insertHelper(node->left, value);
                }
            } 
            else 
            {
                if (node->right == nullptr) 
                {
                    node->right = new TreeNode(value);
                } 
                else 
                {
                    insertHelper(node->right, value);
                }
            }
        }

        void inorder(TreeNode* node) 
        {
            if (node == nullptr) return;
            inorder(node->left);
            cout << node->data << " ";
            inorder(node->right);
        }

        void display() 
        {
            inorder(root);
            cout << endl;
        }
};

int main() 
{
    BinaryTree bt;
    bt.insert(5);
    bt.insert(3);
    bt.insert(7);
    bt.insert(2);
    bt.insert(4);
    bt.insert(6);
    bt.insert(8);
    bt.display();  // 출력: 2 3 4 5 6 7 8
    return 0;
}