Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Node{
- public:
- Node *left;
- Node *right;
- Node *parent;
- private:
- int value;
- public:
- static void DFS(Node *node,int val)
- {
- if(node->left!=NULL)
- DFS(node->left, val);
- if(node->right!=NULL)
- DFS(node->right, val);
- if((node->value)==val)
- {
- if(node->left!=NULL)
- {
- //connect left child to the deleted node's parent
- if(node->parent!=NULL)
- {
- if(node->parent->right==node)
- node->parent->right = node->left;
- else
- if(node->parent->left==node)
- node->parent->left = node->left;
- node->left->parent = node->parent;
- }
- //connect right child to a leaf of the left child's subtree
- if(node->right!=NULL)
- {
- Node *lf = returnLeaf(node->left);
- node->right->parent = lf;
- lf->right = node->right;
- }
- }
- else
- if(node->right!=NULL)
- {
- //connect right child to the deleted node's parent
- if(node->parent!=NULL)
- {
- if(node->parent->right==node)
- node->parent->right = node->right;
- else
- if(node->parent->left==node)
- node->parent->left = node->right;
- node->right->parent = node->parent;
- }
- //connect left child to a leaf of the right child's subtree
- if(node->left!=NULL)
- {
- Node *lf = returnLeaf(node->right);
- node->left->parent = lf;
- lf->right = node->right;
- }
- }
- delete node;
- }
- }
- static Node* returnLeaf(Node *node)
- {
- //returns a leaf of the node's subtree
- if(node->left!=NULL)
- return returnLeaf(node->left);
- if(node->right!=NULL)
- return returnLeaf(node->right);
- return node;
- }
- static Node* removeNodes(Node *node, int value)
- {
- /*
- The question is very ambiguous, because I don't know what should
- I do with the children of a deleted node. Which one should I
- connect to the deleted node's parent? Or should let the graph
- disconnected after the deletion?
- I will connect one of the children to the node's parent,
- and the othe one to a leaf of the first child's subtree
- */
- //Solution:
- while(node->parent!=NULL)
- node = node->parent;
- //Now I am on the root
- DFS(node, value);
- return node;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement