#include <iostream>

#ifndef BINARYTREE_CLASS_INCLUDED
#define BINARYTREE_CLASS_INCLUDED

/*
	Binary Tree Class (BinaryTree)
	LastModification : 2008. 5. 15
	Version : 1.1.0
	myllyj(myllyj at myllyj dot com) / http://program.myllyj.com

	Comment :
		기존 BTree Class는 메소드도 난잡하고, naming이 햇갈리게 되어 있어서
		새롭게 클래스를 작성함.
		새 BinaryTree클래스는 이전 BTree클래스와 전혀 호환이 되지 않으며,
		메소드명명법은 C#형태를 따르고 있음.

	History
		1.1.0 - 트리 깊이 측정 기능 추가
		1.1.0 - 트리 삭제가 아닌 Unlink 기능 추가

*/

template <class T>
class BinaryTree
{
	
private :
	T data;
	BinaryTree<T>* parent;
	BinaryTree<T>* left;
	BinaryTree<T>* right;
	int nowDepth;
	int resultDepth;

	void innerDFS(BinaryTree<T>* node);
	
public:
	BinaryTree();
	BinaryTree(const T& data);
	BinaryTree(const T& data, BinaryTree<T>* parent);


	void SetLeftChild(const T & data);
	void SetLeftChild(BinaryTree<T>* node);
	void SetRightChild(const T & data);
	void SetRightChild(BinaryTree<T>* node);
	void SetParent(BinaryTree<T>* node);

	void RemoveLeftChild();
	void RemoveRightChild();

	BinaryTree<T>* UnlinkLeftChild();
	BinaryTree<T>* UnlinkRightChild();

	int CountChild();

	void SetData(const T & data);
	T GetData();

	BinaryTree<T>* GetLeftChild();
	BinaryTree<T>* GetRightChild();
	BinaryTree<T>* GetParent();

	int GetDepth();

};

template <class T>
BinaryTree<T>::BinaryTree()
{
	this->parent = NULL;
	this->left = NULL;
	this->right = NULL;
}

template <class T>
BinaryTree<T>::BinaryTree(const T &data)
{
	this->parent = NULL;
	this->data = data;
	this->left = NULL;
	this->right = NULL;
}

template <class T>
BinaryTree<T>::BinaryTree(const T &data, BinaryTree<T> *parent)
{
	this->parent = parent;
	this->data = data;
	this->left = NULL;
	this->right = NULL;
}

// BinaryTree가 가지고 있는 Child의 갯수를 반환합니다.
template <class T>
int BinaryTree<T>::CountChild()
{
	int count = 0;

	if (this->left!=NULL) count++;
	if (this->right!=NULL) count++;

	return count;
}

// BinaryTree의 데이터 값을 반환합니다.
template <class T>
T BinaryTree<T>::GetData()
{
	return this->data;
}

// BinaryTree의 데이터 값을 설정합니다.
template <class T>
void BinaryTree<T>::SetData(const T& data)
{
	this->data = data;
}

// 왼쪽 서브트리를 반환합니다.
template <class T>
BinaryTree<T>* BinaryTree<T>::GetLeftChild()
{
	return this->left;
}

// 오른쪽 서브트리를 반환합니다.
template <class T>
BinaryTree<T>* BinaryTree<T>::GetRightChild()
{
	return this->right;
}

// 왼쪽 서브트리를 지정합니다. 지정하는 서브트리의 부모는 현재 트리로 설정됩니다.
template <class T>
void BinaryTree<T>::SetLeftChild(BinaryTree<T> *node)
{
	this->left = node;
	if (this->left!=NULL) this->left->SetParent(this);
}

// 왼쪽 Child에 데이터를 설정합니다.
template <class T>
void BinaryTree<T>::SetLeftChild(const T &data)
{
	this->left = new BinaryTree<T>(data, this);
}

// 오른쪽 서브트리를 지정합니다. 지정하는 서브트리의 부모는 현재 트리로 설정됩니다.
template <class T>
void BinaryTree<T>::SetRightChild(BinaryTree<T> *node)
{
	this->right = node;
	if (this->right!=NULL) this->right->SetParent(this);
}

// 오른쪽 Child에 데이터를 설정합니다.
template <class T>
void BinaryTree<T>::SetRightChild(const T &data)
{
	this->right = new BinaryTree<T>(data, this);
}

// 왼쪽 서브트리를 삭제합니다.
template <class T>
void BinaryTree<T>::RemoveLeftChild()
{
	if (this->left==NULL) return;
	if (this->left->CountChild()==0) delete this->left;
	this->left = NULL;
}

// 오른쪽 서브트리를 삭제합니다.
template <class T>
void BinaryTree<T>::RemoveRightChild()
{
	if (this->right==NULL) return;
	if (this->right->CountChild()==0) delete this->right;
	this->right = NULL;
}

// 부모 트리를 반환합니다.
template <class T>
BinaryTree<T>* BinaryTree<T>::GetParent()
{
	return this->parent;
}

// 부모 트리를 지정합니다.
template <class T>
void BinaryTree<T>::SetParent(BinaryTree<T> *node)
{
	this->parent = node;
}

// 왼쪽 서브트리와 연결을 끊습니다.
template <class T>
BinaryTree<T>* BinaryTree<T>::UnlinkLeftChild()
{
	BinaryTree<T>* result = this->left;
	this->left = NULL;
	return this->left;
}

// 오른쪽 서브트리와 연결을 끊습니다.
template <class T>
BinaryTree<T>* BinaryTree<T>::UnlinkRightChild()
{
	BinaryTree<T>* result = this->right;
	this->right = NULL;
	return this->right;
}

template <class T>
void BinaryTree<T>::innerDFS(BinaryTree<T>* node)
{
	if (node==NULL) return;

	this->nowDepth ++;
	if (nowDepth > this->resultDepth) resultDepth = nowDepth;

	if (node->GetLeftChild()!=NULL)
	{
		this->innerDFS(node->GetLeftChild());
		nowDepth--;
	}

	if (node->GetRightChild()!=NULL)
	{
		this->innerDFS(node->GetRightChild());
		nowDepth--;
	}

	return;
}

// 이 트리의 Depth를 구합니다.
template <class T>
int BinaryTree<T>::GetDepth()
{
	nowDepth = 0;
	resultDepth = 0;
	this->innerDFS(this);
	return this->resultDepth;
}

#endif