SHARE
TWEET

Untitled

a guest Oct 21st, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Node
  2. {
  3. public:
  4.     Node* left;
  5.     Node* right;
  6.     Node* parent;
  7.  
  8.     void setValue(int const value) noexcept
  9.     {
  10.         this->value = value;
  11.     }
  12.  
  13.     inline int getValue() const noexcept
  14.     {
  15.         return value;
  16.     }
  17.  
  18.     static Node* getLeafStarting(Node* start) noexcept
  19.     {
  20.         while(start->left != nullptr) {
  21.             start = start->left;
  22.         }
  23.  
  24.         if(start->right != nullptr) {
  25.             return getLeafStarting(start->right);
  26.         }
  27.  
  28.         return start;
  29.     }
  30.  
  31.     static Node* removeNodes(Node* node, int value)
  32.     {
  33.         Node* current = node;
  34.  
  35.         bool hasLeft = current->left != nullptr;
  36.         bool hasRight = current->right != nullptr;
  37.  
  38.         if(hasLeft) {
  39.             removeNodes(current->left, value);
  40.         }
  41.         if(hasRight) {
  42.             removeNodes(current->right, value);
  43.         }
  44.  
  45.         if(!hasLeft && !hasRight && value == current->getValue()) {
  46.             deleteNode(current);
  47.         }
  48.         else if((!hasLeft || !hasRight) && value == current->getValue()) {
  49.             if(hasLeft) {
  50.                 current->left->parent = current->parent;
  51.             }
  52.             else if(hasRight) {
  53.                 current->right->parent = current->parent;
  54.             }
  55.  
  56.             deleteNode(current);
  57.         }
  58.         else if(hasLeft && hasRight && value == current->getValue()) {
  59.             auto leaf = getLeafStarting(current);
  60.  
  61.             leaf->parent = current->parent;
  62.             leaf->left = current->left;
  63.             leaf->right = current->right;
  64.  
  65.             deleteNode(current);
  66.         }
  67.  
  68.         return node;
  69.     }
  70.  
  71. private:
  72.     int value;
  73.  
  74.     static void deleteNode(Node* node) noexcept
  75.     {
  76.         node->left = nullptr;
  77.         node->right = nullptr;
  78.         node->parent = nullptr;
  79.  
  80.         delete node;
  81.     }
  82. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top