SHARE
TWEET

Untitled

a guest Oct 21st, 2019 72 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. private:
  8.     int value;
  9. public:
  10.     static void DFS(Node *node,int val)
  11.     {
  12.         if(node->left!=NULL)
  13.             DFS(node->left, val);
  14.         if(node->right!=NULL)
  15.             DFS(node->right, val);
  16.         if((node->value)==val)
  17.         {
  18.  
  19.             if(node->left!=NULL)
  20.             {
  21.                 //connect left child to the deleted node's parent
  22.                 if(node->parent!=NULL)
  23.                 {
  24.                     if(node->parent->right==node)
  25.                         node->parent->right = node->left;
  26.                     else
  27.                         if(node->parent->left==node)
  28.                             node->parent->left = node->left;
  29.                     node->left->parent = node->parent;
  30.                 }
  31.                 //connect right child to a leaf of the left child's subtree
  32.                 if(node->right!=NULL)
  33.                 {
  34.                     Node *lf = returnLeaf(node->left);
  35.                     node->right->parent = lf;
  36.                     lf->right = node->right;
  37.                 }
  38.             }
  39.             else
  40.                 if(node->right!=NULL)
  41.                 {
  42.                     //connect right child to the deleted node's parent
  43.                     if(node->parent!=NULL)
  44.                     {
  45.                         if(node->parent->right==node)
  46.                             node->parent->right = node->right;
  47.                         else
  48.                             if(node->parent->left==node)
  49.                                 node->parent->left = node->right;
  50.                         node->right->parent = node->parent;
  51.                     }
  52.  
  53.                     //connect left child to a leaf of the right child's subtree
  54.                     if(node->left!=NULL)
  55.                     {
  56.                         Node *lf = returnLeaf(node->right);
  57.                         node->left->parent = lf;
  58.                         lf->right = node->right;
  59.                     }
  60.                 }
  61.             delete node;
  62.         }
  63.     }
  64.  
  65.     static Node* returnLeaf(Node *node)
  66.     {
  67.         //returns a leaf of the node's subtree
  68.         if(node->left!=NULL)
  69.             return returnLeaf(node->left);
  70.         if(node->right!=NULL)
  71.             return returnLeaf(node->right);
  72.         return node;
  73.     }
  74.  
  75.     static Node* removeNodes(Node *node, int value)
  76.     {
  77.         /*
  78.             The question is very ambiguous, because I don't know what should
  79.             I do with the children of a deleted node. Which one should I
  80.             connect to the deleted node's parent? Or should let the graph
  81.             disconnected after the deletion?
  82.  
  83.             I will connect one of the children to the node's parent,
  84.             and the othe one to a leaf of the first child's subtree
  85.         */
  86.  
  87.         //Solution:
  88.  
  89.         while(node->parent!=NULL)
  90.             node = node->parent;
  91.         //Now I am on the root
  92.         DFS(node, value);
  93.         return node;
  94.     }
  95.  
  96.  
  97. };
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