(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
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
언제가 아닌가프로그래밍 언어에서 null 참조가 수십억 달러의 실수라는 말을 이미 들었을 것입니다. Java의 유명하고 두려운 NullPointerException은 여러분이 알고 있거나 C의 분할 오류일 수 있습니다. 모든 상...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.