*필요 헤더: 링크드 리스트
220407~220411_자료구조_링크드 리스트 구현 (Linked List)
#pragma once //경고메시지를 띄우기 위한 헤더 #include /* 자료구조 : 데이터를 관리하는 방법. * 완벽한 자료구조는 없다. 상황마다 적합하고 효율적인 자료구조가 다르다. 그것을 적재적소에 활용하
hyrule.tistory.com
//Tree.h
/*
* 여태까지 우리가 만들어온 자료구조(리스트, 배열 등) = 선형
* 트리는 이와는 다르게 약간 입체적.
* 최상단에 루트노드가 존재 -> 나뭇가지처럼 루트노드로부터 뻗어나감
* 규칙성있게 트리 형태를 만들어가는 여러 자료구조가 있다.
(이진트리, 쿼드트리, 옥트리 등)
* 물론, 일반적인 형태의 트리도 많이 씀(나중에 3d 애니메이션 나갈때 많이 쓰게 됨)
* 이진트리 = 최대 가지수가 2개(노드가 2개), 쿼드트리 = 4개 옥트리 = 8개
* 이처럼 자식 노드의 개수가 정해져있는 트리들은 리스트, 배열 2가지로 구현이 가능함
* 자식 노드가 계속 트리를 가지는것을 계층, 차수 등으로 부름
* 트리 안에도 트리가 있다고 볼 수 있다.(서브트리)
* 제일 끝에 있는 말단 노드 = 리프(leaf) 노드
* 재귀함수를 이용해서 많이 구현하는 편.
* 일반트리는 리스트 기반으로 구현함(또는 동적 배열)
*/
/*
* 일반적으로 싱글링크드리스트 형태로 구현된다.
* 자식노드가 굉장히 여러개가 되야 할 수도 있음. 그래서 구현방법이 다양함.
1. 모든 자식노드를 담아놓을 수 있는 배열(또는 리스트)을 만든다던지,
2. 노드는 차일드 노드와 형제노드 하나를 가진다.
- 루트는 차일드노드만 있음
- 가장 먼저 생긴 차일드노드가 이후 같은 계층에 생성된 형제 노드들과 연결되는 방식.
3. root 노드가 child 노드 리스트를 가지고 있고, 여기에 모든 child 노드가 들어감
각 노드들도 child 노드들을 가지고 있음
<순서>
1. CTreeNode 클래스 생성
2. CTree 클래스를 friend 등록
3. 우리가 구현해놓은 List 클래스를 이용해
child 클래스 '주소'를 저장할 리스트 생성
4. typedef NODE, PNODE 지정.
5. PNODE m_Root 노드 주소를 저장
*/
#pragma once
#include "LinkedList.h"
/*
* 새로 배운것: template key, value
template <typename KEY, typename VALUE>
- KEY 내가 원하는 노드를 탐색하기 위한 값
- 즉 저장하고자 하는 값에 이름을 부여해준다(라벨을 붙인다고 생각하면 될듯)
- VALUE 내가 찾고자 하는 값
*/
template <typename KEY, typename VALUE>
class CTreeNode
{
template <typename KEY, typename VALUE>
friend class CTree;
private:
CTreeNode():
m_Parent(nullptr)
{
}
~CTreeNode()
{
std::cout << "* " << m_Key << "번 Key 노드 제거 완료." << std::endl;
}
private:
KEY m_Key;
VALUE m_Value;
//부모노드는 하나이므로 포인터, 자식노드는 여러개일수 있으므로 리스트 클래스에 저장.
CTreeNode<KEY, VALUE>* m_Parent;
CList<CTreeNode<KEY, VALUE>*> m_ChildList;
};
template <typename KEY,typename VALUE>
class CTree
{
public:
CTree():
m_Root(nullptr),
m_Size(0)
{
}
~CTree()
{
//재귀 형태로 각 노드의 ChildList에 등록된 노드를 제거한다.
DeleteALL(m_Root);
if(m_Root) delete m_Root;
}
private:
typedef CTreeNode<typename KEY, typename VALUE> NODE;
typedef CTreeNode<typename KEY, typename VALUE>* PNODE;
private:
PNODE m_Root; //최상위의 루트 노드
int m_Size;
public:
/*
* void insert(KEY key, VALUE value, KEY parentkey)
- 3번째 인자를 이용하여 부모가 될 노드 지정
- VALUE에는 넣을 값을 지정
- 첫 번째 인자에는 새로 만들어지는 노드의 키를 지정
- 이렇게 키 값을 부여해놓으면 탐색속도가 다른 자료구조보다 월등히 빠름
- 루트노드가 없을 때의 예외를 지정해서 key와 value로 root를 지정해줌
- 루트노드가 있으면 parentkey를 이용해서 부모 노드를 찾는다.
- 찾는법: KEY & 와 Node 주소를 받고
PNODE를 반환하는 FindNode함수를 통해서
- 노드를 찾았으면 해당 노드를 반환해준다.
- 못찾았으면 현재 노드의 자식노드를 모두 반복하며 자식노드를 기반으로
탐색을 반복한다.
- 찾았으면 해당 주소를 반환하고
- 못 찾았으면 nullptr를 반환한다.
*/
//ParentKey로 찾은 노드의 자식을 Key라는 이름으로 등록. 거기에 데이터 value를 넣는다.
//등록 성공 시 true 반환
bool insert(KEY key, VALUE value, KEY ParentKey)
{
//예외처리 - 루트노드가 존재하지 않으면 루트노드를 생성한다.
if (!m_Root)
{
m_Root = new NODE;
m_Root->m_Key = key;
m_Root->m_Value = value;
++m_Size;
return true;
}
if (FindNode(key))
{
//중복 키가 있을 경우 생성하지 않음
return false;
}
else
{
//부모노드를 찾는다.
PNODE Parent = FindNode(ParentKey, m_Root);
//새 노드를 생성한다.
PNODE NewNode = new NODE;
//새 노드에 Key, Value값을 넣는다.
NewNode->m_Key = key;
NewNode->m_Value = value;
//새 노드를 부모노드에 연결하고, 부모노드에서는
//자식노드 리스트에 해당 노드를 추가한다.
NewNode->m_Parent = Parent;
Parent->m_ChildList.push_back(NewNode);
++m_Size;
return true;
}
}
int getSize()
{
return m_Size;
}
//노드 탐색 함수. 외부에서 키를 받아 내부 private 함수로 처리한다.
//작동하는지 여부를 보기 위해 노드에 저장된 값을 모두 출력하도록 추가
//찾으면 true 반환
public:
bool FindNode(const KEY& Key) const
{
PNODE fnd = FindNode(Key, m_Root);
if (fnd)
{
std::cout << "* FOUND!!" << std::endl;
std::cout << "* Key: " << fnd->m_Key << std::endl;
std::cout << "* Value: " << fnd->m_Value << std::endl;
if (fnd != m_Root)
{
std::cout << "* Parent Key: " << fnd->m_Parent->m_Key << std::endl;
}
std::cout << "* Size of Child Nodes: " << fnd->m_ChildList.size() << std::endl;
std::cout << "==================\n" << std::endl;
return true;
}
else
{
std::cout << "* NOT FOUND!!" << std::endl;
return false;
}
}
private:
PNODE FindNode(const KEY& key, PNODE Node) const
{
//노드를 찾았다면 해당 노드를 반환해준다
if (Node->m_Key == key)
return Node;
//현재 노드의 자식노드를 모두 반복하며
//자식노드를 기반으로 탐색을 재개한다.
//리스트 안에 또 템플릿이 들어오므로
//앞에 typename을 붙여서 CTreeNode<KEY, VALUE>* 또한 타입임을 알려 준다.
typename CList<CTreeNode<KEY, VALUE>*>::iterator iter;
typename CList<CTreeNode<KEY, VALUE>*>::iterator iterEnd = Node->m_ChildList.end();
for (iter = Node->m_ChildList.begin(); iter != iterEnd; ++iter)
{
//자식노드를 넣어주면서 탐색을 재개한다.(재귀함수 호출)
PNODE Result = FindNode(key, *iter);
//탐색한 결과 노드가 있다면 찾았다는 의미이므로
//이 노드를 반환한다.
if (Result)
return Result;
}
//반복이 끝날 때까지 못 찾았다면 찾는 노드가 없다는 것이므로
//nullptr을 반환한다.
return nullptr;
}
//동적할당된 노드들을 제거. 리스트 자체를 제거하는 것이 아니라 리스트 안에 등록된
//동적할당 노드들을 제거해야 한다.
//**루트 노드는 따로 제거를 해 주어야 한다!!**
void DeleteALL(PNODE Node)
{
if (!Node)
return;
typename CList<CTreeNode<KEY, VALUE>*>::iterator iter;
typename CList<CTreeNode<KEY, VALUE>*>::iterator iterEnd = Node->m_ChildList.end();
for (iter = Node->m_ChildList.begin(); iter!=iterEnd; ++iter)
{
PNODE del = *iter;
//std::cout << "* Key " << del->m_Key << " 제거 완료" << std::endl;
if (del)
{
//자식노드들에 대해 DeleteAll 먼저 재귀호출
DeleteALL(del);
delete del;
}
}
}
};
//main.cpp
#include <iostream>
#include "Tree.h"
int main()
{
CTree<int, int>* tree = new CTree<int, int>;
//루트 노드 삽입
tree->insert(0, 0, 0);
//루트노드를 부모노드로 하는 자식노드 1층
for (int i = 1; i <= 5; ++i)
{
tree->insert(i, i, 0);
}
//위 노드들을 부모노드로 하는 자식노드 2층
for (int i = 6; i <= 20; ++i)
{
tree->insert(i, i, i%5 + 1);
}
//위 노드를 부모노드로 하는 자식노드 3층
for (int i = 21; i <= 100; ++i)
{
tree->insert(i, i, i % 15 + 6);
}
//잘 들어갔나 확인
for (int i = 0; i <= 100; ++i)
{
tree->FindNode(i);
}
std::cout << "* Tree Size: " << tree->getSize() << std::endl;
//동적할당된 노드들 젤 제거되나 확인
delete tree;
return 0;
}
'C++기초' 카테고리의 다른 글
| 220415~220418_자료구조_이진트리(Binary Tree) 실행 (0) | 2022.04.22 |
|---|---|
| 220415~220418_자료구조_이진트리(Binary Tree) 구현 (0) | 2022.04.22 |
| 220413_자료구조_배열형 큐(써클 큐, Circle Queue) 구현 및 실행 (0) | 2022.04.18 |
| 220413_자료구조_리스트형 큐 구현 및 실행 (0) | 2022.04.18 |
| 220412_자료구조_배열형 스택 구현 및 실행 (0) | 2022.04.18 |