220414_자료구조_일반 트리(Tree)

*필요 헤더: 링크드 리스트

https://hyrule.tistory.com/45

220407~220411_자료구조_링크드 리스트 구현 (Linked List)

 

//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;
}