220415~220418_자료구조_이진트리(Binary Tree) 구현

* 필요 헤더: LinkedList.h

https://hyrule.tistory.com/45

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

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

	}

};