Facebook
From Beige Cockroach, 6 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 267
  1. #include <memory>
  2. #include "stdafx.h"
  3.  
  4. template<class T>struct Node;
  5.  
  6. template<class T>
  7. struct Node {
  8.         T key;
  9.         std::shared_ptr<Node> left;
  10.         std::shared_ptr<Node> right;
  11.         Node(T);
  12. };
  13.  
  14. template<class T>
  15. Node<T>::Node(T item){
  16.         key = item;
  17.         left = nullptr;
  18.         right = nullptr;
  19. }
  20.  
  21. template<class T>
  22. struct BST {
  23.        
  24.         std::shared_ptr<Node<T>>root;
  25.         BST();
  26.        
  27.         bool insert(T x);
  28.         bool find(T x);
  29.         bool erase(T x);
  30.         Node<T>& min(void);
  31.         Node<T>& max(void);
  32. };
  33.  
  34. template<class T>
  35. bool BST<T>::insert(T val)
  36. {
  37.        
  38. }
  39.  
  40. template<class T>
  41. bool BST<T>::find(T val)
  42. {
  43.         if (root == NULL)
  44.         {
  45.                 std::cout << "tree is empty, cannot find this value" << std::endl;
  46.                 return false;
  47.         }
  48.         else
  49.         {
  50.                 std::shared_ptr<Node<T>> current = root;
  51.                 while (current != NULL)
  52.                 {
  53.                         if (current->key == val)
  54.                         {
  55.                                 std::cout << "Found value: " + current->key << std::endl;
  56.                                 return true;
  57.                         }
  58.                         current = (current->key > val) ? (current->left) : (current->right);
  59.                 }
  60.                 std::cout << "Cannot find this value:"<< std::endl;
  61.                 return false;
  62.         }
  63. }
  64.  
  65. template<class T>
  66. bool BST<T>::erase(T val)
  67. {
  68.  
  69. }
  70.  
  71. template<class T>
  72. Node<T> & BST<T>::min(void)
  73. {
  74.        
  75. }
  76.  
  77. template<class T>
  78. Node<T> & BST<T>::max(void)
  79. {
  80.        
  81. }