Binary Search Tree

 

  1. #include <cstdio>
  2. #include <iostream>
  3.  
  4. template <class Type>
  5. struct bNode {
  6.     Type key;
  7.     bNode *link[2];
  8.     bNode(){
  9.         link[0] = NULL;
  10.         link[1] = NULL;
  11.     }
  12. };
  13.  
  14. template <class Type>
  15. class BinarySearchTree {
  16. private:
  17.     int count;
  18.     bNode<Type> *root;
  19.     void clear(bNode<Type> *&ptr);
  20.     bool search(const Type &item, bNode<Type> *&curr, bNode<Type> *&prev, bool
  21.                 &lr) const;
  22.     inline Type inOrder(bNode<Type> *ptr) const;
  23.     inline int subNodes(bNode<Type> * const &ptr) const;
  24.     int height(bNode<Type>* const &ptr) const;
  25.     bNode<Type>* minmax(bNode<Type> *ptr, const bool &lr) const;
  26. public:
  27.     BinarySearchTree();
  28.     ~BinarySearchTree();
  29.     void clear();
  30.     bool isEmpty() const;
  31.     bool insert(const Type &item);
  32.     bool remove(const Type &item);
  33.     bool search(const Type &item, Type *&ptr) const;
  34.     Type min() const;
  35.     Type max() const;
  36.     int size() const;
  37.     int height() const;
  38. };
  39.  
  40. template <class Type>
  41. void BinarySearchTree<Type>::clear(bNode<Type> *&ptr)
  42. {
  43.     if (ptr != NULL) {
  44.         clear(ptr->link[0]);    // clear left
  45.         clear(ptr->link[1]);    // clear right;
  46.         delete ptr;             // delete recursively
  47.     }
  48. }
  49.  
  50. template <class Type>
  51. bool BinarySearchTree<Type>::search(const Type &item, bNode<Type> *&curr,
  52.                                     bNode<Type> *&prev, bool &lr) const
  53. {
  54.     while(curr != NULL) {
  55.         if (curr->key == item)
  56.             return true;
  57.         lr = (item > curr->key); // check bigger? go left : go right.
  58.         prev = curr;             
  59.         curr = curr->link[lr];
  60.     }
  61.     return false;
  62. }
  63.  
  64. template <class Type>
  65. inline Type BinarySearchTree<Type>::inOrder(bNode<Type> *ptr) const
  66. {
  67.     bool lr = 1;
  68.         Type temp;
  69.         bNode<Type> *prev = ptr;
  70.        
  71.         ptr = ptr->link[1]; // right child.
  72.         // find a node which have no left child in the right subTree.
  73.         // find (neighbor) next item. which of course, have no left child.
  74.         while (ptr->link[0] != NULL) {
  75.                 prev = ptr;
  76.                 ptr = ptr->link[lr = 0];
  77.         }
  78.         prev->link[lr] = ptr->link[1]; // remove the item.
  79.         temp = ptr->key; // save the value of the just removed item.
  80.         delete ptr;
  81.         return temp; // return the value.
  82. }
  83.  
  84. template <class Type>
  85. int BinarySearchTree<Type>::height(bNode<Type>* const &ptr) const
  86. {
  87.         if (ptr == NULL)
  88.                 return 0;
  89.         int lt = height(ptr->link[0]), rt = height(ptr->link[1]);
  90.         if (lt < rt)
  91.                 return 1 + rt;
  92.         return 1 + lt;
  93. }
  94.  
  95. template <class Type>
  96. bNode<Type>* BinarySearchTree<Type>::minmax(bNode<Type> *ptr, const bool &lr) const
  97. {
  98.         // lr = zero min: lr = NOZero, max;
  99.         while (ptr->link[lr] != NULL)
  100.                 ptr = ptr->link[lr];
  101.         return ptr;
  102. }
  103.  
  104. template <class Type>
  105. BinarySearchTree<Type>::BinarySearchTree()
  106. {
  107.         // constructor
  108.         root = NULL;
  109.         count = 0;
  110. }
  111.  
  112. template <class Type>
  113. BinarySearchTree<Type>::~BinarySearchTree()
  114. {
  115.         clear(root);
  116. }
  117.  
  118. template <class Type>
  119. void BinarySearchTree<Type>::clear()
  120. {
  121.         clear(root);
  122.         root = NULL;
  123.         count = 0;
  124. }
  125.  
  126. template <class Type>
  127. bool BinarySearchTree<Type>::isEmpty() const
  128. {
  129.         return (root == NULL);
  130. }
  131.  
  132. template <class Type>
  133. bool BinarySearchTree<Type>::insert(const Type &item)
  134. {
  135.         if (root == NULL) {
  136.                 root = new bNode<Type>;
  137.                 root->key = item;
  138.                 count++;
  139.                 return true;
  140.         }
  141.         bool lr;
  142.         bNode<Type> *curr = root, *prev;
  143.         if (search(item, curr, prev, lr)) // overlap item is not allowed.
  144.                 return false;
  145.         prev->link[lr] = new bNode<Type>;
  146.         prev->link[lr]->key = item;
  147.         count++;
  148.         return true;
  149. }
  150.  
  151. template <class Type>
  152. inline int BinarySearchTree<Type>::subNodes(bNode<Type>* const &ptr) const
  153. {
  154.         if (ptr->link[1] != NULL) {
  155.                 if (ptr->link[0] != NULL) // have two childs
  156.                         return 2;
  157.                 else
  158.                         return 1;  // have only one child
  159.         } else if (ptr->link[0] != NULL)
  160.                 return 1; // have only one child.
  161.         else
  162.                 return 0; // have no child
  163. }
  164.  
  165. template <class Type>
  166. bool BinarySearchTree<Type>::remove(const Type &item)
  167. {
  168.         bool lr = 1;
  169.         bNode<Type> *curr = root, *prev;
  170.         if (!search(item, curr, prev, lr))
  171.                 return false;
  172.         switch (int s = subNodes(curr)) {
  173.         // get the number of childs.
  174.         case 0:
  175.         case 1:
  176.                 if (curr == root)
  177.                         root = curr->link[(s > 0)];
  178.                 else
  179.                         prev->link[lr] = curr->link[(s > 0)];
  180.                 delete curr;
  181.                 break;
  182.         case 2:
  183.                 curr->key = inOrder(curr); // replace the value with the next(neighbour) item's
  184.         }
  185.         count--;
  186.         return true;
  187. }
  188.  
  189. template <class Type>
  190. bool BinarySearchTree<Type>::search(const Type &item, Type *&ptr) const
  191. {
  192.         bool found;
  193.         bNode<Type> *curr = root, *prev;
  194.         found = search(item, curr, prev, found);
  195.         ptr = &curr->key;
  196.         return found;
  197. }
  198.  
  199. template <class Type>
  200. Type BinarySearchTree<Type>::min() const
  201. {
  202.     return minmax(root, 0)->key;
  203. }
  204.  
  205. template <class Type>
  206. Type BinarySearchTree<Type>::max() const
  207. {
  208.     return minmax(root, 1)->key;
  209. }
  210.  
  211. template <class Type>
  212. int BinarySearchTree<Type>::size() const
  213. {
  214.     return count;
  215. }
  216.  
  217. template <class Type>
  218. int BinarySearchTree<Type>::height() const
  219. {
  220.     return height(root);
  221. }
  222.  
  223. int main(int argc, char **argv)
  224. {
  225.         BinarySearchTree<int> *bst = new BinarySearchTree<int>();
  226.         //               8
  227.         //             /   \
  228.         //            7     9
  229.         //           / \   /  \
  230.         //          5   4 10  11
  231.         bst->insert(8);
  232.         bst->insert(7);
  233.         bst->insert(9);
  234.         bst->insert(5);
  235.         bst->insert(4);
  236.         bst->insert(10);
  237.         bst->insert(11);
  238.         std::cout << bst->height()  << std::endl;
  239.         std::cout << bst->min() << std::endl;
  240.         std::cout << bst->max() << std::endl;
  241.         std::cout << bst->size() << std::endl;
  242.         std::cout << bst->remove(8) << std::endl;
  243.         std::cout << bst->size() << std::endl;
  244.         std::cout << bst->height()  << std::endl;
  245.         delete bst;
  246.         return 0;
  247. }

Algorithm binary search tree c++ Comments(0) 2008年10月19日 08:25







Host by is-Programmer.com | Power by Chito 1.3.3 beta | Designed by Wink Hosting.