Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void del (int key)
- {
- Node* KeyPointer;
- Node* current;
- Node* parent;
- Node* temp;
- KeyPointer = pRoot;
- while (KeyPointer->iData != key) //finding the pointer with key data
- {
- if (KeyPointer->iData > key)
- {
- KeyPointer = KeyPointer->pLeftChild;
- }
- else if (KeyPointer->iData < key)
- {
- KeyPointer = KeyPointer->pRightChild;
- }
- } //when loop ends, KeyPointer will be pointer with key
- if (KeyPointer = NULL)
- {
- cout << "Node to be deleted is NULL" << endl;
- }
- else if (KeyPointer->pRightChild == NULL && KeyPointer->pLeftChild == NULL) //case 1: No child
- {
- temp = KeyPointer;
- KeyPointer = NULL;
- delete temp;
- }
- else if (KeyPointer->pRightChild == NULL) //case 2: one child
- {
- temp = KeyPointer;
- KeyPointer = KeyPointer->pLeftChild;
- delete temp;
- }
- else if (KeyPointer->pLeftChild == NULL)
- {
- temp = KeyPointer;
- KeyPointer = KeyPointer->pRightChild;
- delete temp;
- }
- else //case 3: two child
- {
- current = KeyPointer->pRightChild; //smallest of right subtree approach
- parent = NULL;
- while (current->pLeftChild != NULL)
- {
- parent = current;
- current = current->pLeftChild;
- }
- KeyPointer->iData = current->iData; //swapping data
- if (parent == NULL) //did not traverse,
- {
- KeyPointer->pRightChild = current->pRightChild;
- }
- else //to link any subtrees under deleted node
- {
- parent->pLeftChild = current->pRightChild;
- }
- delete current;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement