20210804 이진 트리 순회, erase

안녕하세요 틴구입니다

오늘은 어제배운 이진트리에서 erase에 관한 녀석들을 적어보도록 할게요

우선 순회라는 녀석에 대해서 설명해드리도록 하겠습니다

이진트리는 3가지의 순회방법이 있습니다

이진트리 순회방법

전위순회, 중위순회, 후위순회
전위순회 : Root -> Left -> Right 의 순서로 구성되어 있고

중위순회 : Left -> Root -> Right 의 순서로 구성되어 있고
후위순회 : Left -> Right -> Root 의 순서로 구서되어 있습니다.

(어제의 코드에서 이어짐)

public:
    void PreOrder(void(*pFunc)(const KEY&, const VALUE&))
    {
        PreOrder(pFunc, m_Root);
    }

    void InOrder(void(*pFunc)(const KEY&, const VALUE&))

    {
        InOrder(pFunc, m_Root);
    }

    void PostOrder(void(*pFunc)(const KEY&, const VALUE&))

    {
        PostOrder(pFunc, m_Root);
    }

 

private:

     void PreOrder(void(*pFunc)(const KEY&, const VALUE&), PNODE Node)
    {
        if (!Node)
            return;

        pFunc(Node->first, Node->second);
        PreOrder(pFunc, Node->m_Left);
        PreOrder(pFunc, Node->m_Right);
    }

    void InOrder(void(*pFunc)(const KEY&, const VALUE&), PNODE Node)
    {
        if (!Node)
            return;

        InOrder(pFunc, Node->m_Left);
        pFunc(Node->first, Node->second);
        InOrder(pFunc, Node->m_Right);
    }

    void PostOrder(void(*pFunc)(const KEY&, const VALUE&), PNODE Node)
    {
        if (!Node)
            return;

        PostOrder(pFunc, Node->m_Left);
        PostOrder(pFunc, Node->m_Right);
        pFunc(Node->first, Node->second);
    }

 

위처럼 헤더파일에 코드를 구성하고 메인함수에서

void Output(const int& Key, const int& Value)
{
std::cout << "Key : " << Key << " Value : " << Value << " => ";
}

CBinaryTree<int, int> tree;

tree.insert(5, 5);
tree.insert(3, 3);
tree.insert(1, 1);
tree.insert(4, 4);
tree.insert(10, 10);
tree.insert(8, 8);
tree.insert(15, 15);
tree.insert(9, 9);

 

CBinaryTree<int, int>::iterator iter;

std::cout << "=========== PreOrder ===========" << std::endl;
tree.PreOrder(Output);
std::cout << std::endl;

std::cout << "=========== InOrder ===========" << std::endl;
tree.InOrder(Output);
std::cout << std::endl;

std::cout << "=========== PostOrder ===========" << std::endl;
tree.PostOrder(Output);
std::cout << std::endl;
std::cout << std::endl;

for (iter = tree.begin(); iter != tree.end(); ++iter)
{
std::cout << "key : " << iter->first << " value : " <<
iter->second << std::endl;
}

위처럼 메인함수 코드를 진행하고 출력을 하게되면

 

=========== PreOrder ===========
Key : 5 Value : 5 => Key : 3 Value : 3 => Key : 1 Value : 1 => Key : 4 Value : 4 => Key : 10 Value : 10 => Key : 8 Value : 8 => Key : 9 Value : 9 => Key : 15 Value : 15 =>
=========== InOrder ===========
Key : 1 Value : 1 => Key : 3 Value : 3 => Key : 4 Value : 4 => Key : 5 Value : 5 => Key : 8 Value : 8 => Key : 9 Value : 9 => Key : 10 Value : 10 => Key : 15 Value : 15 =>
=========== PostOrder ===========
Key : 1 Value : 1 => Key : 4 Value : 4 => Key : 3 Value : 3 => Key : 9 Value : 9 => Key : 8 Value : 8 => Key : 15 Value : 15 => Key : 10 Value : 10 => Key : 5 Value : 5 =>

 

의 코드가 나오게 됩니다. 중위순회의 경우 정령이 되어 나오는것을 볼 수 있습니다.

아래의 코드는 erase에 관한 코드 구성 및 분석입니다.

erase

    iterator erase(const KEY& key)
    {
        iterator iter = Find(key);  // iter 변수에 Find(key)를 넣어 사용자가 찾는 키를 넣어준다

        if (iter == end())  // Find에서 못찾았을 경우 end()를 반환하도록 하였기때문에 여기서도 iter == end()일 경우 
            return iter;      // iter를 반환해준다.

        return erase(iter);  // 그게 아니라면 erase(iter)함수를 반환
    }

    iterator erase(const iterator& iter)
    {

        // 이 부분은 예외처리이다.
        if (iter == end())
            return iter;

        else if (iter == m_Begin)
            return end();

        else if (iter.m_Node == nullptr)
            return end();

        // 리프노드일 경우 부모로부터 연결을 제거하고 노드를 제거해준다.
        if (!iter.m_Node->m_Left && !iter.m_Node->m_Right)
        {
            // 부모노드를 얻어온다.
            PNODE Parent = iter.m_Node->m_Parent;

            // 만약 부모노드가 없다면 현재 지우려는 노드는 루트노드라는 것이다.
            // 그런데 루트노드가 리프노드라는 말은 이 노드 1개만 남았다는
            // 것이다.
            if (!Parent)
            {
                delete iter.m_Node;

                m_Root = nullptr;
                --m_Size;

                // 다 지웠으니 Begin과 End끼리 연결한다.
                m_Begin->m_Next = m_End;
                m_End->m_Prev = m_Begin;

                return end();
            }

            // 지우려는 노드가 부모느드의 왼쪽 노드인지 오른쪽 노드인지를
            // 판단하여 부모와의 연결을 끊어준다.
            if (Parent->m_Left == iter.m_Node)
                Parent->m_Left = nullptr;

            else
                Parent->m_Right = nullptr;

            // 리스트 연결
            PNODE Prev = iter.m_Node->m_Prev;
            PNODE Next = iter.m_Node->m_Next;

            Prev->m_Next = Next;
            Next->m_Prev = Prev;

            delete iter.m_Node;

            --m_Size;


            // 지운 노드의 다음노드를 넣어서 iterator를 반환해준다.
            iterator result;
            result.m_Node = Next;

            return result;
        }

        // 만약 왼쪽 노드가 있을 경우 왼쪽 노드에서 가장 큰 노드를 찾아서
        // 지울 노드의 값을 변경해주고 찾아준 노드를 제거한다.
        if (iter.m_Node->m_Left)
        {
            // 왼쪽에 존재하는 노드들중 가장 큰 노드를 찾아온다.
            PNODE MaxNode = FindMax(iter.m_Node->m_Left);

            // 찾아준 노드의 Key, Value 값으로 변경해준다.
            iter.m_Node->first = MaxNode->first;
            iter.m_Node->second = MaxNode->second;

            // 찾아준 노드를 제거해야하기 때문에 부모로부터 연결을 끊고
            // 제거해주도록 한다.
            // 단, 찾아준 노드가 왼쪽 자식노드가 있을수도 있으므로
            PNODE LeftChild = MaxNode->m_Left;
            PNODE Parent = MaxNode->m_Parent;

            if (Parent->m_Left == MaxNode)
                Parent->m_Left = LeftChild;

            else
                Parent->m_Right = LeftChild;

            // 왼쪽 자식노드가 있을 경우라면 부모로 MaxNode의 부모를
            // 지정해주도록 한다.
            if (LeftChild)
                LeftChild->m_Parent = Parent;

            PNODE Prev = MaxNode->m_Prev;
            PNODE Next = MaxNode->m_Next;

            Prev->m_Next = Next;
            Next->m_Prev = Prev;

            delete MaxNode;

            --m_Size;

            iterator result;
            result.m_Node = Next;

            return result;
        }

        // 지울 노드의 오른쪽 노드만 존재할 경우 오른쪽 노드에서 가장 작은 노드를
        // 찾아온다.
        PNODE MinNode = FindMin(iter.m_Node->m_Right);

        // 찾아준 노드의 Key, Value 값으로 변경해준다.
        iter.m_Node->first = MinNode->first;
        iter.m_Node->second = MinNode->second;

        // 찾아준 노드를 제거해야하기 때문에 부모로부터 연결을 끊고
        // 제거해주도록 한다.
        // 단, 찾아준 노드가 오른쪽 자식노드가 있을수도 있으므로
        PNODE RightChild = MinNode->m_Right;
        PNODE Parent = MinNode->m_Parent;

        if (Parent->m_Left == MinNode)
            Parent->m_Left = RightChild;

        else
            Parent->m_Right = RightChild;

        // 오른쪽 자식노드가 있을 경우라면 부모로 MinNode의 부모를
        // 지정해주도록 한다.
        if (RightChild)
            RightChild->m_Parent = Parent;

        PNODE Prev = MinNode->m_Prev;
        PNODE Next = MinNode->m_Next;

        Prev->m_Next = Next;
        Next->m_Prev = Prev;

        delete MinNode;

        --m_Size;

        iterator result;
        result.m_Node = Next;

        return result;
    }

private:
    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);
    }

    void PreOrder(void(*pFunc)(const KEY&, const VALUE&), PNODE Node)
    {

        // 노드가 nullptr일 경우는 바로 return해준다.
        if (!Node)
            return;
        // 전위순회의 경우 루트 레프트 라이트의 순서기때문에

        // 함수에 들어오자마자 루트의 KEY, VAlUE값을 얻어온다
        pFunc(Node->first, Node->second);

        // 그리고 그 루트의 좌측의값을 얻어온다
        PreOrder(pFunc, Node->m_Left);

        // 위 두개의 함수까지 끝냈다면 라이트노드의 값을 얻어온다.
        PreOrder(pFunc, Node->m_Right);
    }

    void InOrder(void(*pFunc)(const KEY&, const VALUE&), PNODE Node)
    {
        if (!Node)
            return;

        InOrder(pFunc, Node->m_Left);
        pFunc(Node->first, Node->second);
        InOrder(pFunc, Node->m_Right);
    }

    void PostOrder(void(*pFunc)(const KEY&, const VALUE&), PNODE Node)
    {
        if (!Node)
            return;

        PostOrder(pFunc, Node->m_Left);
        PostOrder(pFunc, Node->m_Right);
        pFunc(Node->first, Node->second);
    }

    PNODE FindMax(PNODE Node)
    {

        // 만약에 노드의 m_Right가 있을경우 Node->m_Right를 반환해주어 Max값이 나올때까지 반환해준다.
        if (Node->m_Right)
            return FindMax(Node->m_Right);

        return Node;
    }

    PNODE FindMin(PNODE Node)
    {

        // 만약에 노드의 m_Left가 있을경우 Node->m_Left를 반환해주어 Min값이 나올때까지 반환해준다.
        if (Node->m_Left)
            return FindMin(Node->m_Left);

        return Node;
    }
};

여기까지 배운코드를 선생님 주석 + 저가 코드 분석한 주석을 추가로 달아보았습니다!!