20210803 이진 트리 (재귀 함수 활용)

안녕하세요 틴구입니다!

오늘은 이진 트리에 대해서 알아보도록 합시다!!

이진트리 정의

이진트리란 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 합니다.

이진트리는 탐색하는데에 있어서 최적화 되어있다고 합니다.

정확한 이진 트리의 정의는 위키백과 주소 달아놓을게요!

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC

이진 트리 - 위키백과, 우리 모두의 백과사전

우선 이진트리 맨 꼭대기에 있는 것을 루트라고합니다

루트 + 자식노드 or 부모노드 + 자식노드 = 서브트리라고 합니다

자식이 없는 노드는 리프노드구요

또 한개가 트리에서 한개의 노드가 빠져있는 형태를 완전 이진트리라고 하고

전부 꽉차있는 형태를 포화 이진트리라고 합니다

한쪽으로 치우쳐있는 형태는 편향 트리라고 하구요.

 

또 이진트리 말고 쿼드트리, 옥트리도 있다고 합니다

쿼드 트리 = 자식이 최대 4개까지 가능

옥트리 = 자식이 최대 8개까지 가능.

 

그럼 오늘 배운 내용에 대해서 코드 분석을 해볼까요

BinaryTree.h (인라인 생성)

#pragma once

template <typename KEY, typename VALUE>
class CBinaryTreeNode
{
    template <typename KEY, typename VALUE>
    friend class CBinaryTree;
    template <typename KEY, typename VALUE>
    friend class CBinaryTreeIterator;

private:
    CBinaryTreeNode() :
        m_Left(nullptr),
        m_Right(nullptr),
        m_Parent(nullptr),
        m_Next(nullptr),
        m_Prev(nullptr)
    {
    }

    ~CBinaryTreeNode()
    {
    }

private:
    CBinaryTreeNode<KEY, VALUE>* m_Left; // 왼쪽 자식노드의 주소를 저장하기 위한 변수
    CBinaryTreeNode<KEY, VALUE>* m_Right; // 오른쪽 자식노드의 주소를 저장하기 위한 변수
    CBinaryTreeNode<KEY, VALUE>* m_Parent;   // 부모 노드의 주소를 저장하기 위한 변수
    CBinaryTreeNode<KEY, VALUE>* m_Next; // 이터레이터 방식으로 돌리기위한 Next변수
    CBinaryTreeNode<KEY, VALUE>* m_Prev; // Prev변수

public:
    KEY first;
    VALUE second;
};

template <typename KEY, typename VALUE>
class CBinaryTreeIterator
{
    template <typename KEY, typename VALUE>
    friend class CBinaryTree;

public:
    CBinaryTreeIterator() :
        m_Node(nullptr)
    {
    }

    ~CBinaryTreeIterator()
    {
    }

private:
    CBinaryTreeNode<KEY, VALUE>* m_Node;

public:
    // iterator끼리 서로 가지고 있는 노드가 같을 경우 같다고 판단한다.
    bool operator == (const CBinaryTreeIterator<KEY, VALUE>& iter) const
    {
        return m_Node == iter.m_Node;
    }

    bool operator != (const CBinaryTreeIterator<KEY, VALUE>& iter) const
    {
        return m_Node != iter.m_Node;
    }

    bool operator == (const CBinaryTreeNode<KEY, VALUE>* Node) const
    {
        return m_Node == Node;
    }

    bool operator != (const CBinaryTreeNode<KEY, VALUE>* Node) const
    {
        return m_Node != Node;
    }

    void operator ++ ()
    {
        m_Node = m_Node->m_Next;
    }

    void operator ++ (int)
    {
        m_Node = m_Node->m_Next;
    }

    void operator -- ()
    {
        m_Node = m_Node->m_Prev;
    }

    void operator -- (int)
    {
        m_Node = m_Node->m_Prev;
    }

    CBinaryTreeNode<KEY, VALUE>* operator -> ()
    {
        return m_Node;
    }
};

// Key는 탐색을 하기 위한 타입이다.
// Value는 실제 저장하기 위한 데이터 타입이다.
// 그래서 탐색을 할때는 Key타입으로 한다.
// 만약 Key타입이 문자열이라면 문자열로 탐색을 할 수 있는 것이다.
template <typename KEY, typename VALUE>
class CBinaryTree
{
public:
    CBinaryTree()
    {
        m_Root = nullptr;
        m_Size = 0;

        m_Begin = new NODE;
        m_End = new NODE;

        m_Begin->m_Next = m_End;
        m_End->m_Prev = m_Begin;
    }

    ~CBinaryTree()
    {
        PNODE DeleteNode = m_Begin;

        while (DeleteNode)
        {
            PNODE Next = DeleteNode->m_Next;

            delete DeleteNode;

            DeleteNode = Next;
        }
    }

private:
    typedef CBinaryTreeNode<KEY, VALUE> NODE;
    typedef CBinaryTreeNode<KEY, VALUE>* PNODE;

public:
    typedef CBinaryTreeIterator<KEY, VALUE> iterator;

private:
    PNODE m_Root;
    PNODE m_Begin;
    PNODE m_End;
    int m_Size;

public:
    void insert(const KEY& key, const VALUE& value)
    {
        // 처음 데이터를 추가할 경우
        if (!m_Root)
        {
            // 새로운 루트 변수에 동적할당을 한다
            m_Root = new NODE;
            // first에 key를 저장
            // second에 value를 저장
            m_Root->first = key;
            m_Root->second = value;
            
            // m_Begin 과 m_End 사이에 m_Root를 넣어준다
            m_Begin->m_Next = m_Root;
            m_Root->m_Prev = m_Begin;

            m_Root->m_Next = m_End;
            m_End->m_Prev = m_Root;
        }

        else
        {
            insert(key, value, m_Root);
        }

        ++m_Size;
    }

    int size() const
    {
        return m_Size;
    }

    bool empty() const
    {
        return m_Size == 0;
    }

    iterator begin() const
    {
        iterator iter;
        iter.m_Node = m_Begin->m_Next;
        return iter;
    }

    iterator end() const
    {
        iterator iter;
        iter.m_Node = m_End;
        return iter;
    }

    iterator Find(const KEY& key) const
    {
        return Find(key, m_Root);
    }

private:
    PNODE insert(const KEY& key, const VALUE& value, PNODE Node)
    {
        // 기준노드보다 작다면 왼쪽이다.
        if (Node->first > key)
        {
            // 만약 기준노드의 왼쪽 자식노드가 있다면 그 왼쪽 자식노드를
            // 기준노드로 하여 다시 탐색을 하게 한다.
            if (Node->m_Left)
                return insert(key, value, Node->m_Left);

            // 더이상 왼쪽 자식노드가 없을 경우 이 위치에 새로 노드를 생성하여
            // 추가해주어야 한다.
            PNODE NewNode = new NODE;

            NewNode->first = key;
            NewNode->second = value;

            // 기준노드의 왼쪽 자식노드로 지정한다.
            Node->m_Left = NewNode;
            NewNode->m_Parent = Node;

            // 왼쪽으로 배치가 된다는것은 부모노드보다 작다는 것이다.
            // 그러므로 부모노드의 이전노드와 부모노드 사이에 새로 생성된
            // 노드를 리스트로 연결해주도록 한다.
            PNODE Prev = Node->m_Prev;

            Prev->m_Next = NewNode;
            NewNode->m_Prev = Prev;

            NewNode->m_Next = Node;
            Node->m_Prev = NewNode;

            return NewNode;
        }

        // 여기로 내려오면 값이 크다는 것이므로 오른쪽으로 탐색을 해봐야 한다.
        // 만약 오른쪽 자식노드가 있을 경우 기준노드를 오른쪽 자식노드로 하여
        // 탐색하게 한다.
        if (Node->m_Right)
            return insert(key, value, Node->m_Right);

        // 더이상 오른쪽 자식노드가 없을 경우 이 위치에 새로 노드를 생성하여
        // 추가해주어야 한다.
        PNODE NewNode = new NODE;

        NewNode->first = key;
        NewNode->second = value;

        // 기준노드의 오른쪽 자식노드로 지정한다.
        Node->m_Right = NewNode;
        NewNode->m_Parent = Node;

        PNODE Next = Node->m_Next;

        Node->m_Next = NewNode;
        NewNode->m_Prev = Node;

        NewNode->m_Next = Next;
        Next->m_Prev = NewNode;

        return NewNode;
    }

    iterator Find(const KEY& key, PNODE Node) const
    {
        // 기준노드가 nullptr일 경우 더이상 탐색할 노드가 없으므로
        // end를 리턴한다. 못찾았다는 것이다.
        if (!Node)
            return end();

        if (Node->first == key)
        {
            iterator iter;
            iter.m_Node = Node;
            return iter;
        }

        // 키를 비교하여 작으면 왼쪽, 크면 오른쪽으로 탐색해서 들어간다.
        if (Node->first > key)
            return Find(key, Node->m_Left);

        return Find(key, Node->m_Right);
    }
};

main.cpp

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

int main()
{
    srand((unsigned int)time(0));
    rand();

    CBinaryTree<int, int> Tree;

    for (int i = 0; i < 10; ++i)
    {
        // key와 value값에 랜덤한수를 넣어줍니다.
        int Number = rand() % 101 + 1;
        Tree.insert(Number, Number);
    }
    // 이터레이터 변수 생성
    CBinaryTree<int, int>::iterator iter;
    // 처음 begin() 부터 end()가 아닐때까지 계속 돌려주어 코드블록의 내용을 출력한다.
    for (iter = Tree.begin(); iter != Tree.end(); ++iter)
    {
        std::cout << "key : " << iter->first << " value : " << iter->second << std::endl;
    }
    // Finde를 이용해서 본인이 원하는 값을 찾는다
    iter = Tree.Find(50);
    // Find함수 생성할때 찾지 못했을경우 end()를 리턴하게 해둬서
    // iter == Tree.end()를 하면 못찾았을때의 텍스트를 출력하게 한다.
    if (iter == Tree.end())
    {
        std::cout << "찾는데이터가 없습니다." << std::endl;
    }
    
    // 그게 아니라 찾았으면 그 값들을 출력하게 된다.
    else
    {
        std::cout << "Find key : " << iter->first << " Finde value : " << iter->second << std::endl;
    }


    return 0;
}

위의 코드를 출력하게 되면

랜덤한 수의 key value값이 10번 정렬되어 출력이되고 마지막으로 찾는 숫자가 랜덤한 수가 있으면

그 값의 key와 value가 밑에 출력이 되고 찾는 숫자가 없으면 찾는 데이터가 없습니다 라고 뜨게됩니다.

오늘은 여기까지 알아보도록 하고 내일 다시 돌아올게요~~