#include
using?namespace?std;
template?
class?BinaryTreeNode
{
public:
	T?element;
	BinaryTreeNode?*leftChild;
	BinaryTreeNode?*rightChild;
	BinaryTreeNode（）?{}
	~BinaryTreeNode（）
	{
		if?（leftChild）?delete?leftChild;
		if?（rightChild）?delete?rightChild;
	}
};
template
void?create（BinaryTreeNode**?root）
{
	T?temp;
	cin?>>?temp;
	if?（temp?==?0）
	{
		*root?=?NULL;
	}
	else?{
		*root?=?new?BinaryTreeNode;
		（*root）->element?=?temp;
		create（&（（*root）->leftChild））;
		create（&（（*root）->rightChild））;
	}
}
int?flag?=?0;
template
BinaryTreeNode*?search（BinaryTreeNode*rootT?key）
{
	BinaryTreeNode*?current?=?root;
	while?（（NULL）?!=?root?&&?（key?!=?current->element））
	{
		current?=?（key?element???search（current->leftChild?key）?:?search（current->rightChild?key））;
		if?（current?==?NULL）break;
	}
	return?current;
}
template?
BinaryTreeNode*?getParent（BinaryTreeNode*root?BinaryTreeNode*current）
{
	BinaryTreeNode*temp?=?root;
	BinaryTreeNode*temp2?=?root;
	while?（temp）
	{
		if?（current->element?>?temp->element）
		{
			temp2?=?temp;
			temp?=?temp->rightChild;
		}
		if?（current->element?element）
		{
			temp2?=?temp;
			temp?=?temp->leftChild;
		}
		if?（current->element?==?temp->element）
		{
			return?temp2;
		}
	}
	return?NULL;
}
template
void?insertNode（BinaryTreeNode*rootconst?T?&value）
{
	BinaryTreeNode*p?=?root?*prev?=?NULL;
	while?（p!=NULL）
	{
		??prev?=?p;
		if?（p->element?			p?=?p->rightChild;
		else
			p?=?p->leftChild;
	}
	if?（root?==?NULL）
	{
		root?=?new?BinaryTreeNode;
		root->element?=?value;
	}
	else?if?（prev->element?	{
		prev->rightChild?=?new?BinaryTreeNode;
		prev->rightChild->element?=?value;
	}
	else?{
		prev->leftChild?=?new?BinaryTreeNode;
		prev->leftChild->element?=?value;
	}
}
template?
void?deleteNode（BinaryTreeNode*rootconst?T?&value）
{
	BinaryTreeNode*node=search（rootvalue）;
	if?（node?==?NULL）
	{
		cout?<	}
	if?（value?==?root->element）
	{
		BinaryTreeNode*temp?=?root->leftChild;
		while?（temp->rightChild?!=?NULL）
		{
			temp?=?temp->rightChild;
		}
		BinaryTreeNode*temp2?=?getParent（roottemp）;
		root->element?=?temp->element;
		temp2->rightChild?=?temp->leftChild;
	}
	else
	{
		BinaryTreeNode*prevNode?=?getParent（root?node）;//刪除結點前一節點
		int?flag?=?0;
		if?（prevNode->leftChild?==?node）
			flag?=?1;
		BinaryTreeNode*tmp?=?nod