[자료구조] 트리 (Tree)

트리 TREE

 

트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고,

서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다.

또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다.

자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*])라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다. 

 

트리 (Tree)

 

 

 

트리 구조란 계층적인 구조를 가지는 자료형태를 말합니다.

노드로 구성된 자료구조이며, 회사의 조직구조 , 계층적인 데이터 저장 등에 사용됩니다.

 

위에 그림의 경우 루트 노드(트리 구조에서 최상위에 존재하는 노드)는 A이며, 내부 노드(아래로 다른 노드가 연결되어 있는 노드)는 B, C ,D ,E ,H 입니다.

 

나머지 단말 노드(아래로 다른 노드가 연결되어 있지 않는 노드)는 K,L ,F ,G ,M ,I J 입니다.

트리의 레벨(깊이 , 루트 노드로 부터의 단계)은 4입니다.

 

일반적으로 트리 구조의 경우  하나의 노드가 여러개의 자식 노드를 가질 수 있습니다.

 

이진 트리 (Binary Tree)

 

최대 2개의 자식을 가지는 트리구조를 이진트리라고 합니다.

 

완전 이진 트리 (Complete Binary Tree)

 

 

노드가 위에서 아래로 왼쪽에서 오른쪽 순서대로 모두 채워진 상태를 말합니다.

즉 각 레벨당 비어있는 왼쪽과 오른쪽 노드가 비어있지 않은 상태의 트리구조를 말합니다.

 

포화 이진 트리 (Full Binary Tree)

 

 

모든 레벨이 꽉 차있는 상태를 말합니다. 

즉, 노드를 추가하려면 레벨이 증가가 필요한 상태를 말합니다.

 

[코드 구현]

#include <iostream>

using namespace std;

class Node
{

public  :

    int data;
    Node* left;
    Node* right;

    Node()
        : data(-1), left(nullptr), right(nullptr) {}    
};

class Tree
{
private :

    Node* root;

    Node* FindNode(int _data)
    {
        Node* node = root;

        while (node != nullptr)
        {
            if (node->data < _data)
            {
                node = node->left;
            }
            else if (node->data > _data)
            {
                node = node->right;
            }
            else
            {
                break;
            }            
        }
        return node;
    }

public :

    Tree() : root(nullptr) {}

    void Insert(int _data)
    {
        Node* node = new Node();
        node->data = _data;
        
        if (root != nullptr)
        {
            Node* target = root;
            bool Isinsert = false;

            while (!Isinsert)
            {
                if (target->data > _data) // 데이터가 크면 왼쪽으로 정렬
                {
                    if (target->left != nullptr)
                    {
                        target = target->left;
                    }
                    else
                    {
                        target->left = node;
                        Isinsert = true;
                    }
                }
                else if (target->data < _data) // 데이터가 작으면 오른쪽으로 정렬
                {
                    if (target->right != nullptr)
                    {
                        target = target->right;
                    }
                    else
                    {
                        target->right = node;
                        Isinsert = true;
                    }
                }
                else // 예외처리 (ex. 같은 숫자의 경우)
                {        
                    Isinsert = true;
                    cout << "Insert Fail !" << endl;

                    delete node;
                    node = nullptr;                    
                }
            }
        }
        else // root 가 비어있을 경우 
        {
            root = node;
        }
    }

    void Delete(int _data)
    {
        Node* node = root;
        Node* parentNode = nullptr;

        while (node != nullptr)
        {            
            if (node->data > _data) // 데이터가 작으면 왼쪽으로 찾는다.
            {
                parentNode = node;
                node = node->left;
            }
            else if (node->data < _data) // 데이터가 크면 오른쪽으로 찾는다.
            {
                parentNode = node;
                node = node->right;
            }
            else // 찾았을 경우 (같은 숫자 확인)
            {
                //노드를 삭제한 후 삭제한 노드의 자식중 하나가 들어갈 위치를 결정
                Node** target = nullptr;

                if (node != root) // root일 경우 삭제하지 않는다.
                {
                    // 삭제할 노드가 부모 노드의 왼쪽인지 오른쪽인지를 확인한다.        
                    if (parentNode->data > _data)
                    {
                        target = &(parentNode->left);
                    }
                    else
                    {
                        target = &(parentNode->right);
                    }
                }
                else
                {
                    target = &(root);
                }

                //삭제할 노드의 자식들 처리부분
                if (node->left == nullptr && node->right == nullptr)
                {
                    (*target) = nullptr;
                }
                else if (node->left != nullptr && node->right == nullptr)
                {
                    (*target) = node->left;
                }
                else if (node->left == nullptr && node->right != nullptr)
                {
                    (*target) = node->right;
                }
                else
                {
                    (*target) = node->left;
                    Node* childNode = node->left;
                    while (childNode->right != nullptr)
                    {
                        childNode = childNode->right;
                    }
                    childNode->right = node->right;
                }

                //실제로 삭제
                delete node;
                node = nullptr;
            }
        }
    }

    void Print()
    {
        cout << "Tree Print------------------------" << endl;
        Print(root);
        cout << "\n----------------------------------\n" << endl;
    }

    void Print(Node* node)
    {
        if (node)
        {
            Print(node->left);
            cout << node->data << " ";
            Print(node->right);
        }
    }

};


int main()
{
    Tree tree;

    tree.Insert(10);
    tree.Insert(5);
    tree.Insert(20);
    tree.Insert(6);
    tree.Insert(15);

    tree.Print();
    tree.Delete(5);
    tree.Print();

// -- 결과
//Tree Print------------------------
//5 6 10 15 20
//----------------------------------

//Tree Print------------------------
//6 10 15 20
//----------------------------------

    return 0;
}