ツリーc++テンプレートクラス実装

template 
class Link {
public:
	T element;
	Link *leftchild;
	Link *rightchild;
};

template
class BST : private Link {
	typedef Link Node;
	typedef Link* NodePo;
public:
	BST();
	~BST();
	void Insert(T &element);
	void Delete(T &element);
	void Destroy();
	void PreDisplay();                   //    
private:
	NodePo root;
	void PreDisplay(NodePo p);         //    
	NodePo Destroy(NodePo p);            //      
	NodePo Insert(NodePo p, T &element); //      
	NodePo Delete(NodePo p, T &element); //      
	NodePo FindMin(NodePo p) const;      //         
	NodePo FindMax(NodePo p) const;      //         
};

template
BST::BST() {
	root = NULL; //      
}

template
BST::~BST() {
	Destroy();   //      
}

template
void BST::Insert(T &element) {
	root = Insert(root, element);
}

template
Link* BST::Insert(NodePo p, T &element) {
	if (!p) {
		p = new Node;
		p->element = element;
		p->leftchild = NULL;
		p->rightchild = NULL;
	}
	else {
		if (element < p->element) //Go Left
			p->leftchild = Insert(p->leftchild, element);
		else if (element > p->element) // Go right
			p->rightchild = Insert(p->rightchild, element);
		else { //           
		}
	}
	return p;
}

template
void BST::Delete(T &element) {
		root = Delete(root, element);
}

template
Link* BST::Delete(NodePo p, T &element) {
	NodePo temp;
	cout << "successful
";
	system("pause");
	if (!p) { //          
	}
	else {
		if (element < p->element) { //Go left
			cout << "Go left
";
			system("pause");
			p->leftchild = Delete(p->leftchild, element);
		}
		else if(element > p->element) { //Go right
			cout << "Go right
";
			system("pause");
			p->rightchild = Delete(p->rightchild, element);
		}
		else if(p->leftchild && p->rightchild) { //two child
			cout << "two child value:" << p->element << endl;
			temp = FindMin(p->rightchild);
			p->element = temp->element;
			element = temp->element;
			p->rightchild = Delete(p->rightchild, element);
		}
		else{   // one child
			temp = p;
			cout << "one child value:" << p->element << endl;
			system("pause");
			if (p->leftchild) //p    
				p = p->leftchild;
			else if (p->rightchild) //p        
				p = p->rightchild;
			else
				p = NULL;
			delete temp;
		}
	}
	return p;
}

template
Link* BST::FindMin(NodePo p) const{ //   
	if (!p) {
		cout << "can't find Min" << endl;
	}
	else {
		while (p->leftchild)
			p = p->leftchild;
	}
	return p;
}

template
Link* BST::FindMax(NodePo p) const{  //   
	if(!p)
		cout << "can't find Max" << endl;
	else
		while (p->rightchild)
			p = p->rightchild;
	return p;
}

template
void BST::PreDisplay() {
	PreDisplay(root);
}

template
void BST::PreDisplay(NodePo p) {
	if (!p) {
		return;
	}
	cout << p->element << endl;
	PreDisplay(p->leftchild);
	PreDisplay(p->rightchild);
	return;
}

template
void BST::Destroy() {
	root = Destroy(root);
}

template
Link* BST::Destroy(NodePo p) {
	if (p == NULL ) {
	}
	else{
		p->leftchild = Destroy(p->leftchild);
		p->rightchild = Destroy(p->rightchild);
		delete p;
	}
	return p;
}