* 필요 헤더: LinkedList.h
220407~220411_자료구조_링크드 리스트 구현 (Linked List)
#pragma once //경고메시지를 띄우기 위한 헤더 #include /* 자료구조 : 데이터를 관리하는 방법. * 완벽한 자료구조는 없다. 상황마다 적합하고 효율적인 자료구조가 다르다. 그것을 적재적소에 활용하
hyrule.tistory.com
//BinaryTree.h
/*
[이진트리]
* 자식노드가 최대 2개
* 구현방식: 배열기반 or 리스트기반
* 배열기반은 복잡하므로 이진트리로
* 이진트리를 쓰는 이유 : '탐색'이 매우 빠르다
- 추가할때, 삭제할때 규칙이 있음
ex) 루트노드보다 큰건 오른쪽, 작은건 왼쪽에 추가
->이래서 루트노드가 작은 수일 경우 한쪽으로만 추가될수도 있다 = 편향트리
만약 이럴경우 리스트보다 느려질 수 있다.
->이 문제점을 해결한 트리 = 균형 이진트리(레드블랙트리가 대표적)
- 추가 구현은 쉬우나 삭제 구현이 어렵다.
*/
//데이터 관리의 용이성을 위해 Binary Tree와 Linked List 형식을 결합할 것임.
#pragma once
#include <iostream>
#include "LinkedList.h"
//KEY값: 저장규칙 - 대소판별, VALUE값: 실제 들어갈 데이터
template <typename KEY, typename VALUE>
class CBinaryTreeNode
{
template <typename KEY, typename VALUE>
friend class CBinaryTree;
template <typename KEY, typename VALUE>
friend class CBinaryTreeIterator;
public:
CBinaryTreeNode():
m_Parent(nullptr),
m_Left(nullptr),
m_Right(nullptr),
m_Next(nullptr),
m_Prev(nullptr)
{
}
~CBinaryTreeNode()
{
}
public:
//정보 저장
VALUE m_Data;
//현재 노드의 키값
KEY m_Key;
private:
//(트리노드)부모노드, 좌, 우 노드 저장
CBinaryTreeNode<KEY, VALUE>* m_Parent;
CBinaryTreeNode<KEY, VALUE>* m_Left;
CBinaryTreeNode<KEY, VALUE>* m_Right;
//(링크드리스트)앞노드, 뒤노드 저장
CBinaryTreeNode<KEY, VALUE>* m_Next;
CBinaryTreeNode<KEY, VALUE>* m_Prev;
};
template <typename KEY, typename VALUE>
class CBinaryTreeIterator
{
template <typename KEY, typename VALUE>
friend class CBinaryTree;
//밖에서 실제로 활용해야 할 기능이기 때문에 public으로 선언
public:
CBinaryTreeIterator():
m_Node(nullptr)
{
}
~CBinaryTreeIterator()
{
}
private:
CBinaryTreeNode<KEY, VALUE>* m_Node;
public:
//연산자 추가
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);
}
void operator ++ ()
{
m_Node = m_Node->m_Next;
}
void operator -- ()
{
m_Node = m_Node->m_Prev;
}
void operator ++ (int)
{
m_Node = m_Node->m_Next;
}
void operator -- (int)
{
m_Node = m_Node->m_Prev;
}
void operator + (int addnum)
{
for (int i = 0; i < addnum; ++i)
{
if (nullptr == m_Node->m_Next)
return;
m_Node = m_Node->m_Next;
}
}
void operator - (int addnum)
{
for (int i = 0; i < addnum; ++i)
{
if (nullptr == m_Node->m_Prev)
return;
m_Node = m_Node->m_Prev;
}
}
VALUE& operator *()
{
return m_Node->m_Data;
}
//iterator.m_Node를 하지 않아도 바로 m_Node 주소를 반환해 주는 연산자 재정의
CBinaryTreeNode<KEY, VALUE>* operator -> () const
{
return m_Node;
}
};
template <typename KEY, typename VALUE>
class CBinaryTree
{
public:
CBinaryTree() :
m_Root(nullptr)
{
m_Begin = new NODE;
m_End = new NODE;
m_Begin->m_Next = m_End;
m_End->m_Prev = m_Begin;
}
~CBinaryTree()
{
PNODE Del = m_Begin;
while (Del)
{
PNODE Next = Del->m_Next;
delete Del;
Del = Next;
}
}
private:
typedef CBinaryTreeNode<KEY, VALUE> NODE;
typedef CBinaryTreeNode<KEY, VALUE>* PNODE;
typedef CBinaryTreeIterator<KEY, VALUE> iterator;
//루트 노드의 주소 관리
PNODE m_Root;
//링크드 리스트 주소 관리
PNODE m_Begin;
PNODE m_End;
int m_Size;
public:
//기본 기능들 구현.
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;
}
int getsize() const
{
return m_Size;
}
void clear()
{
if (m_Size == 0)
return;
PNODE del = m_Begin->m_Next;
PNODE end = m_End;
while (del != end)
{
PNODE next = del->m_Next;
delete del;
del = next;
}
m_Begin->m_Next = m_End;
m_End->m_Prev = m_Begin;
m_Root = nullptr;
m_Size = 0;
}
//////////////////////////////////////////
public:
//삽입 기능 구현
void insert(const KEY& Key, const VALUE& Value)
{
//루트 노드가 생성되어 있지 않다면 생성
if (!m_Root)
{
//트리 부분
m_Root = new NODE;
m_Root->m_Key = Key;
m_Root->m_Data = Value;
//리스트 부분
m_Root->m_Next = m_End;
m_Root->m_Prev = m_Begin;
m_Begin->m_Next = m_Root;
m_End->m_Prev = m_Root;
++m_Size;
}
else
{
//이외의 경우 재귀호출 시작
PNODE NewNode = insert(Key, Value, m_Root);
}
}
private:
//재귀호출용 오버라이드 함수
PNODE insert(const KEY& Key, const VALUE& Value, PNODE Node)
{
if (!Node)
return nullptr;
//인자로 들어온 노드의 키 값이 Key보다 작을 경우
if (Node->m_Key > Key)
{
//m_Left값이 존재하지 않으면 바로 추가.
if (!Node->m_Left)
{
//트리 부분
PNODE NewNode = new NODE;
NewNode->m_Data = Value;
NewNode->m_Key = Key;
//부모-자식 관계로 연결.
Node->m_Left = NewNode;
NewNode->m_Parent = Node;
////////////////////////////
//리스트 부분
//m_Left에 들어가는 상황이므로 부모 노드의 키 값은 무조건 나보다 크다.
//연결을 위해 임시로 주소를 받아놓고
PNODE Prev = Node->m_Prev;
NewNode->m_Prev = Prev;
NewNode->m_Next = Node;
Prev->m_Next = NewNode;
Node->m_Prev = NewNode;
++m_Size;
//새로 만들어진 노드 주소를 반환
return NewNode;
}
//m_Left값이 존재하면 한번 더 타고들어가는 재귀함수 호출.
return insert(Key, Value, Node->m_Left);
}
//인자로 들어온 노드의 키 값이 Key보다 클 경우
if (Node->m_Key < Key)
{
//m_Left값이 존재하지 않으면 바로 추가.
if (!Node->m_Right)
{
//트리 부분
PNODE NewNode = new NODE;
NewNode->m_Data = Value;
NewNode->m_Key = Key;
//부모-자식 관계로 연결.
Node->m_Right = NewNode;
NewNode->m_Parent = Node;
////////////////////////////
//리스트 부분
//m_Right에 들어가는 상황이므로 부모 노드의 키 값은 무조건 나보다 크다.
//연결을 위해 임시로 주소를 받아놓고
PNODE Next = Node->m_Next;
NewNode->m_Next = Next;
NewNode->m_Prev = Node;
Next->m_Prev = NewNode;
Node->m_Next = NewNode;
//////////////////////////
++m_Size;
return NewNode;
}
//m_Right값이 존재하면 한번 더 타고들어가는 재귀함수 호출.
return insert(Key, Value, Node->m_Right);
}
}
////////////////////////////////////////////////////////////////////
public:
//키값을 입력하면 삭제해주는 기능
iterator erase(const KEY& key)
{
iterator iter = Find(key);
if (iter == end())
return end();
//본체에 찾은 iterator을 넣어 검색
return erase(iter);
}
//erase 본체는 이거
//삭제 후에도 규칙을 유지할 수 있어야 하므로 추가나 탐색보다 훨씬 복잡하다.
iterator erase(const iterator& iter)
{
if (iter == end())
return end();
//1-1. 리프노드인지 확인한다.(리프노드면 바로 삭제하면 되므로)
if (!iter.m_Node->m_Left && !iter.m_Node->m_Right)
{
//(예외처리)혹시나 지울 대상이 마지막 남은 루트노드라면
//(자식이 없는 루트노드 -> 노드가 딱 하나라는 뜻)
//해당 루트노드를 삭제하고 end()를 반환
if (iter.m_Node == m_Root)
{
m_Begin->m_Next = m_End;
m_End->m_Prev = m_Begin;
delete iter.m_Node;
m_Root = nullptr;
--m_Size;
return end();
}
//1-2. 지울 노드가 오른쪽 노드인지 왼쪽 노드인지 확인한다.
if (iter.m_Node->m_Parent->m_Left == iter.m_Node)
{
//이진트리 부모자식관계 정리
iter.m_Node->m_Parent->m_Left = nullptr;
}
else
{
iter.m_Node->m_Parent->m_Right = nullptr;
}
//1-3. 링크드리스트 제거
PNODE Next = iter.m_Node->m_Next;
PNODE Prev = iter.m_Node->m_Prev;
Next->m_Prev = Prev;
Prev->m_Next = Next;
//1-4. 노드 제거
delete iter.m_Node;
//1-5. 사이즈 하나 감소
--m_Size;
//1-6. 삭제된 노드의 다음 노드를 반복자에 담아 반환.
iterator result;
//Next가 end()로 반환될 경우 에러가 났는지 헷갈릴수도 있으므로
//end 바로 전인 Prev를 반환.
if (Next = end().m_Node)
{
result.m_Node = Prev;
return result;
}
result.m_Node = Next;
return result;
}
//2-1. 리프 노드가 아니라면,
//2.2. 그리고, 왼쪽 노드가 존재한다면 왼쪽 노드의 '최댓값'을
// 지울 노드의 위치로 가져온다.
//참고)왼쪽 노드의 최댓값은 절대로 오른쪽 노드를 가지지 않는다.
// 왼쪽 노드의 최댓값의 오른쪽 자식 노드 = 최댓값보다 더 큰 값이여야 함
// -> 말이 안됨.
//하지만, 왼쪽 자식 노드는 가질 수도 있다.
//이 경우, 왼쪽 자식 노드를 부모 노드 위치로 가져온다.
PNODE FindNode = nullptr;
PNODE ChildNode = nullptr;
if (iter.m_Node->m_Left)
{
//왼쪽 노드의 최댓값 탐색
FindNode = FindMax(iter.m_Node->m_Left);
//자식 노드 주소를 받아옴. 없다면 nullptr을 받아올 것임.
ChildNode = FindNode->m_Left;
}
//만약 왼쪽 노드가 존재하지 않을 경우, 오른쪽 노드의 값을 가져온다.
else
{
FindNode = FindMin(iter.m_Node->m_Right);
ChildNode = FindNode->m_Right;
}
//가져온 값을, 지울 키값의 노드에 복사.
iter.m_Node->m_Key = FindNode->m_Key;
iter.m_Node->m_Data = FindNode->m_Data;
//찾은 왼쪽 노드 중 최댓값 / 오른쪽 노드 중 최솟값은
//이진트리의 규칙 상 절대로 자식 노드를 두개 가질 수 없다.
//잘 생각해보자.
//왼쪽 노드 중 최댓값이 오른쪽 노드가 있다면,
//그 값이 최댓값이여야 한다.
//마찬가지로 오른쪽 노드 중 최솟값이 왼쪽 노드가 있다면,
//그 값이 최솟값이여야 한다.
if(FindNode == FindNode->m_Parent->m_Left)
{
FindNode->m_Parent->m_Left = ChildNode;
}
else if (FindNode == FindNode->m_Parent->m_Right)
{
FindNode->m_Parent->m_Right = ChildNode;
}
//그리고 만약 자식노드가 있었다면
//해당 노드를 find노드의 부모 노드와 연결한다.
if (ChildNode)
{
ChildNode->m_Parent = FindNode->m_Parent;
}
//링크드 리스트 정리
//연결시켜주어야 하는 노드는
//FindNode 노드의 prev와 next이다.(왼쪽, 오른쪽 동일)
FindNode->m_Prev->m_Next = FindNode->m_Next;
FindNode->m_Next->m_Prev = FindNode->m_Prev;
//최종적으로 FindNode를 제거한다.
delete FindNode;
//그리고 지운 값이 있던 노드를 반환한다
//(해당 노드는 새 값으로 변경되었음)
iterator result;
result.m_Node = iter.m_Node;
--m_Size;
return result;
}
//////////////////////////////////////////////////////////////////////
private:
//기준 노드의 오른쪽으로 쭉 타고 가면 최댓값이 나온다.
PNODE FindMax(PNODE Node)
{
if (!Node->m_Right)
return Node;
return FindMax(Node->m_Right);
}
//반대로 똑같이
PNODE FindMin(PNODE Node)
{
if (!Node->m_Left)
return Node;
return FindMax(Node->m_Left);
}
//탐색 함수
public:
iterator Find(const int& Key) const
{
return Find(Key, m_Root);
}
private:
iterator Find(const int& Key, PNODE Node) const
{
if (!Node)
return end();
//일치하는 키를 찾으면 이터레이터에 해당 노드를 담아서 리턴
if(Node->m_Key == Key)
{
iterator iter;
iter.m_Node = Node;
return iter;
}
//만약 키 값이 노드의 키보다 작으면 왼쪽으로 탐색
else if (Node->m_Key > Key)
{
return Find(Key, Node->m_Left);
}
//if문을 전부 통과해도 못 찾았을 경우 오른쪽으로 탐색 시작
return Find(Key, Node->m_Right);
}
//전위순회: 루트->왼쪽->오른쪽 순
//중위순회: 왼쪽->루트->오른쪽 순
//후위순회: 왼쪽->오른쪽->루트 순(리프노드부터)
//함수의 재귀구조는 동일하고, 출력 순서만 바꿔주면 됨.
public:
void PreOrder(void (*Func)(const int&, const int&, const int&, const int&, const int&))
{
PreOrder(Func, m_Root);
}
private:
void PreOrder(void (*Func)(const int&, const int&, const int&, const int&, const int&), PNODE Node)
{
if (!Node)
return;
int ParentKey = 0, RightKey = 0, LeftKey = 0;
if (Node->m_Parent)
ParentKey = Node->m_Parent->m_Key;
if (Node->m_Right)
RightKey = Node->m_Right->m_Key;
if (Node->m_Left)
LeftKey = Node->m_Left->m_Key;
Func(Node->m_Key, Node->m_Data, ParentKey, LeftKey, RightKey);
PreOrder(Func, Node->m_Left);
PreOrder(Func, Node->m_Right);
}
public:
void InOrder(void (*Func)(const int&, const int&, const int&, const int&, const int&))
{
InOrder(Func, m_Root);
}
private:
void InOrder(void (*Func)(const int&, const int&, const int&, const int&, const int&), PNODE Node)
{
if (!Node)
return;
int ParentKey = 0, RightKey = 0, LeftKey = 0;
if (Node->m_Parent)
ParentKey = Node->m_Parent->m_Key;
if (Node->m_Right)
RightKey = Node->m_Right->m_Key;
if (Node->m_Left)
LeftKey = Node->m_Left->m_Key;
InOrder(Func, Node->m_Left);
Func(Node->m_Key, Node->m_Data, ParentKey,LeftKey, RightKey);
InOrder(Func, Node->m_Right);
}
public:
void PostOrder(void (*Func)(const int&, const int&, const int&, const int&, const int&))
{
PostOrder(Func, m_Root);
}
private:
void PostOrder(void (*Func)(const int&, const int&, const int&, const int&, const int&), PNODE Node)
{
if (!Node)
return;
int ParentKey = 0, RightKey = 0, LeftKey = 0;
if (Node->m_Parent)
ParentKey = Node->m_Parent->m_Key;
if (Node->m_Right)
RightKey = Node->m_Right->m_Key;
if (Node->m_Left)
LeftKey = Node->m_Left->m_Key;
PostOrder(Func, Node->m_Left);
PostOrder(Func, Node->m_Right);
Func(Node->m_Key, Node->m_Data, ParentKey, LeftKey, RightKey);
}
};'C++기초' 카테고리의 다른 글
| 220419_자료구조_자가균형트리_AVL트리(AVL Tree) 구현 (0) | 2022.04.24 |
|---|---|
| 220415~220418_자료구조_이진트리(Binary Tree) 실행 (0) | 2022.04.22 |
| 220414_자료구조_일반 트리(Tree) (0) | 2022.04.20 |
| 220413_자료구조_배열형 큐(써클 큐, Circle Queue) 구현 및 실행 (0) | 2022.04.18 |
| 220413_자료구조_리스트형 큐 구현 및 실행 (0) | 2022.04.18 |
