Facebook
From Morose Parrot, 6 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 226
  1. #include <memory>
  2. #include "stdafx.h"
  3.  
  4. template<class T>struct NodeType;
  5.  
  6. template<class T>
  7. struct NodeType {
  8.         T key;
  9.         std::shared_ptr<NodeType> left;
  10.         std::shared_ptr<NodeType> right;
  11.         NodeType(T);
  12. };
  13.  
  14. template<class T>
  15. NodeType<T>::NodeType(T myItem){
  16.         key = myItem;
  17.         left = nullptr;
  18.         right = nullptr;
  19. }
  20.  
  21. template<class T>
  22. struct BTS {
  23.         std::shared_ptr<NodeType<T>>root;
  24.         BTS();
  25.        
  26.         bool insert(T);
  27.         bool find(T x);
  28.         bool erase(T x);
  29.         NodeType<T>& min(void);
  30.         NodeType<T>& max(void);
  31. };
  32.  
  33. template<class T>
  34. BTS<T>::BTS() : root(nullptr) {}
  35.  
  36. template<class T>
  37. bool BTS<T>::insert(T val)
  38. {
  39.         std::shared_ptr<NodeType<T>> temp = std::make_shared<NodeType<T>>(val);
  40.        
  41.         if (root == NULL)
  42.         {
  43.                 root = temp;
  44.                 return true;
  45.         }
  46.         else
  47.         {
  48.                 std::shared_ptr<NodeType<T>> current = root;
  49.                 std::shared_ptr<NodeType<T>> parent = root;
  50.  
  51.                 current = (temp->key < current->key) ? (current->left) : (current->right);
  52.                 while (current != NULL)
  53.                 {
  54.                         parent = current;
  55.                         current = (temp->key < current->key) ? (current->left) : (current->right);
  56.                 }
  57.  
  58.                 if (temp->key < parent->key)
  59.                 {
  60.                         parent->left = temp;
  61.                         return true;
  62.                 }
  63.                 else if (temp->key > parent->key)
  64.                 {
  65.                         parent->right = temp;
  66.                         return true;
  67.                 }
  68.                 return false;
  69.         }
  70. }
  71.  
  72. template<class T>
  73. bool BTS<T>::find(T val)
  74. {
  75.         if (root == NULL)
  76.         {
  77.                 std::cout << "tree is empty, cannot find this value" << std::endl;
  78.                 return false;
  79.         }
  80.         else
  81.         {
  82.                 std::shared_ptr<NodeType<T>> current = root;
  83.                 while (current != NULL)
  84.                 {
  85.                         if (current->key == val)
  86.                         {
  87.                                 std::cout << "Found value: " + current->key << std::endl;
  88.                                 return true;
  89.                         }
  90.                         current = (current->key > val) ? (current->left) : (current->right);
  91.                 }
  92.                 std::cout << "Cannot find this value:"<< std::endl;
  93.                 return false;
  94.         }
  95. }
  96.  
  97. template<class T>
  98. bool BTS<T>::erase(T val)
  99. {
  100.  
  101.         if (root == NULL)
  102.         {
  103.                 return false;
  104.         }
  105.         else
  106.         {
  107.                 std::shared_ptr<NodeType<T>> current = root;
  108.                 std::shared_ptr<NodeType<T>> parent = root;
  109.                 std::shared_ptr<NodeType<T>> parent = root;
  110.  
  111.                 current = (val < current->key) ? (current->left) : (current->right);
  112.                 while (current != NULL)
  113.                 {
  114.                         if (current->key == val)
  115.                         {
  116.                                 if (parent->right == current) {
  117.                                         parent->right = current->left;
  118.                                 }
  119.                                 else
  120.                                         parent->left = current->right;
  121.                                 current.reset();
  122.                         }
  123.                         parent = current;
  124.                         current = (key < current->key) ? (current->left) : (current->right);
  125.                 }
  126.  
  127.                 if (temp->key < parent->key)
  128.                 {
  129.                         parent->left = temp;
  130.                         return true;
  131.                 }
  132.                 else if (temp->key > parent->key)
  133.                 {
  134.                         parent->right = temp;
  135.                         return true;
  136.                 }
  137.                 return false;
  138.         }
  139. }
  140.  
  141. template<class T>
  142. NodeType<T> & BTS<T>::min(void)
  143. {
  144.         std::shared_ptr<NodeType<T>> temp = root;
  145.  
  146.         if (root == NULL)
  147.                 throw ("sth wrong");
  148.         else
  149.         {
  150.                 while (temp->left != NULL)
  151.                 {
  152.                         temp = temp->left;
  153.                 }
  154.                 return *temp;
  155.         }
  156. }
  157.  
  158. template<class T>
  159. NodeType<T> & BTS<T>::max(void)
  160. {
  161.         std::shared_ptr<NodeType<T>> temp = root;
  162.  
  163.         if (root == NULL)
  164.                 throw("is not elemnt in the tree");
  165.         else
  166.         {
  167.                 while (temp->right != NULL)
  168.                 {
  169.                         temp = temp->right;
  170.                 }
  171.                 std::cout << temp->key << std::endl;
  172.                 return *temp;
  173.         }
  174. }