Advertisement
Guest User

Untitled

a guest
Jul 26th, 2017
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1. void del (int key)
  2. {
  3. Node* KeyPointer;
  4. Node* current;
  5. Node* parent;
  6. Node* temp;
  7.  
  8. KeyPointer = pRoot;
  9. while (KeyPointer->iData != key) //finding the pointer with key data
  10. {
  11. if (KeyPointer->iData > key)
  12. {
  13. KeyPointer = KeyPointer->pLeftChild;
  14. }
  15. else if (KeyPointer->iData < key)
  16. {
  17. KeyPointer = KeyPointer->pRightChild;
  18. }
  19. } //when loop ends, KeyPointer will be pointer with key
  20.  
  21. if (KeyPointer = NULL)
  22. {
  23. cout << "Node to be deleted is NULL" << endl;
  24. }
  25.  
  26. else if (KeyPointer->pRightChild == NULL && KeyPointer->pLeftChild == NULL) //case 1: No child
  27. {
  28. temp = KeyPointer;
  29. KeyPointer = NULL;
  30. delete temp;
  31. }
  32.  
  33. else if (KeyPointer->pRightChild == NULL) //case 2: one child
  34. {
  35. temp = KeyPointer;
  36. KeyPointer = KeyPointer->pLeftChild;
  37. delete temp;
  38. }
  39.  
  40. else if (KeyPointer->pLeftChild == NULL)
  41. {
  42. temp = KeyPointer;
  43. KeyPointer = KeyPointer->pRightChild;
  44. delete temp;
  45. }
  46.  
  47. else //case 3: two child
  48. {
  49. current = KeyPointer->pRightChild; //smallest of right subtree approach
  50. parent = NULL;
  51.  
  52. while (current->pLeftChild != NULL)
  53. {
  54. parent = current;
  55. current = current->pLeftChild;
  56. }
  57.  
  58. KeyPointer->iData = current->iData; //swapping data
  59.  
  60. if (parent == NULL) //did not traverse,
  61. {
  62. KeyPointer->pRightChild = current->pRightChild;
  63. }
  64.  
  65. else //to link any subtrees under deleted node
  66. {
  67. parent->pLeftChild = current->pRightChild;
  68. }
  69.  
  70. delete current;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement