(2011.08.08) 두 갈래 찾기 트리

//      

/***************************************************************************************
  BST(Binary Search Tree)                      。
             K,       , BST   K,          
 K,     。               。BST             
    。
 ****************************************************************************************/

// The Dictionary abstract class. KEComp compares a key
// and an element. EEComp compares two elements.
template <class Key, class Elem, class KEComp, class EEComp>
class Dictionary
{
public:
	// Reninitialize dictionary
	virtual void clear() = 0;
	// Insert an element. Return true if insert is successful, false otherwise.
	virtual bool insert(const Elem&) = 0;
	// Remove some element matching Key. Return true if such exists, false otherwise. 
	// If multiple entries match key, an arbitrary one is removed.
	virtual bool remove (const Key&, Elem&) = 0;
	// Remove and return an arbitrary element from dictionary.
	// Return true if some element is found, false otherwise.
	virtual bool removeAny(Elem&) = 0;
	// Return a copy of some elem matching Key. Return true if such exists, false otherwise.
	// If multiple elements match Key, return an arbitrary one.
	virtual bool find(const Key&,  Elem&) const = 0;
	// Return the number of elements in the dictionary. 
	virtual int size() = 0;
};

 // Binary Search Tree implementation for the dictionrary ADT
template <class Key, class Elem, class KEComp, class EEComp>
class BST : public Dictionary <Key, Elem, KEComp, EEComp>
{
private:
	BinNode<Elem>* root;				// Root of the BST
	int nodecount;								// Number of nodes in the BST
	// Private "helper" functions
	void clearhelp(BinNode<Elem>*);
	BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&);
	BinNode<Elem>* deletemin(BinNode<Elem>*, BinNode<Elem> *&);
	BinNode<Elem>* removehelp(BinNode<Elem>*, const Key&, BinNode<Elem>*&);
	bool findhelp(BinNode<Elem>*, const Key&, Elem&) const;
	void printhelp(BinNode<Elem>*, int) const;
public:
	BST()									{root = NULL; nodecount = 0; }
	~BST()									{clearhelp(root);}
	void clear()							{clearhelp(root); root = NULL; nodecount = 0;}
	bool insert(const Elem& e)	 {root = inserthelp(root, e);	nodecount++; return true;}
	bool remove(const Key& K, Elem& e)
	{
		BinNode<Elem>* t = NULL;
		root = removehelp(root, K, t);
		if (t == NULL) return false;						// Nothing found
		e = t ->val();
		nodecount--;
		delete t;
		return true;
	}
	bool removeAny(Elem& e)							// Delete min value
	{
		if (root == NULL)				return false;		// empty tree
		BinNode<Elem>* t;
		root = deletemin(root, t);
		e = t -> val();
		delete t;
		nodecount--;
		return true;
	}
	bool find(const Key& K, Elem& e) const
	{
		return findhelp(root, K, e);
	}
	int size()							{return nodecount;}
	void print() const
	{
		if (root == NULL) cout << "The BST is empty". 
"; else printhelp(root, 0); } }; // , , , , , , , , , 。 template <class Key, class Elem, class KEComp, class EEComp> bool BST<Key, Elem, KEComp, EEComp>:: findhelp(BinNode<Elem>* subroot, const Key& K, Elem& e) const { if (subroot == NULL) // empty tree return false; else if (KEComp::lt(K, subroot -> val())) // Check left return findhelp(subroot -> left(), K, e); else if (KEComp::gt(K, subroot -> val())) // Check right return findhelp(subroot -> right(), K, e); else // Found It { e = subroot -> val(); return true; } } template <class Key, class Elem, class KEComp, class EEComp> bool BST<Key, Elem, KEComp, EEComp>:: deletemin(BinNode<Elem>* rubroot, BinNode<Elem>*& min) { if (subroot() == NULL) // Found min { min = subroot; return subroot -> right(); } else { // Continue left subroot -> setLeft(deletemin(subroot -> left(), min)); return subroot; } } template <class Key, class Elem, class KEComp, class EEComp> void BST<Key, Elem, KEComp, EEComp>:: clear help(BinNode<Elem>* subroot) { if (subroot == NULL) return; clearhelp(subroot -> left()); clearhelp(subroot -> right()); delete subroot; } template<class Key, class Elem, class KEComp, class EEComp> BinNode<Elem>* BST <Key, Elem, KEComp, EEComp> :: removehelp(BinNode<Elem>* subroot, const Key& K, BinNode<Elem>*& t) { if(subroot == NULL) return NULL; // Val is not in tree else if (KEComp::lt(K, subroot -> val())) // check left subroot -> setleft(removehelp(subroot -> left(), K, t)); else if (KEComp::gt(K, subroot -> val())) // check right subroot -> setRight(removehelp(subroot -> right(), K, t)); else // Found it: remove it { BinNode<Elem> * temp; t = subroot; if (subroot -> left() == NULL) // Only a right child subroot = subroot -> right(); // So point to right else if (subroot -> right() == NULL) // Only a left child subroot = subroot -> left(); // so point to left else // Both children are non-empty { subroot -> setRight(deletemin(subroot -> right(), temp)); Elem te = sbroot -> val(); subroot -> setVal(temp -> val()); temp -> setVal(te); t = temp; } } return subroot; } template <class Key, class Elem, class KEComp, class EEComp> void BST<Key, Elem, KEComp, EEComp>::printhelp(BinNode<Elem>* subroot, int level) const { if (subroot == NULL) return ; // Empty tree print help(subroot -> left(), level + 1); // Do left subtree for (int i = 0; i < level; i++) // Indent to level cout << " "; cout << subroot -> val() << "
"; // Print node value printhelp(subroot -> right(), level + 1); // Do right subrtree }

좋은 웹페이지 즐겨찾기