//DELETION FROM A BINARY TREE

void testDelete (treePtr &root)

{

int idToDelete;

bool success;

cout << "Testing delete algorithm" << endl << endl;

cout << "Enter Id value to delete (-1 to quit) ---> ";

cin >> idToDelete;

while (idToDelete >= 0)

{

success = deleteNode (root, idToDelete);

cout << "Id # " << idToDelete;

if (!success)

cout << "     No such part in stock" << endl;

else

cout << "     Id #" << idToDelete << " was deleted" << endl;

cout << endl << "Enter Id value to delete (-1 to quit) ---> ";

cin >> idToDelete;

}

}

bool deleteNode (treePtr &p, int idToDelete)

// will recursively search for node with idToDelete, if found, calls modifyTree

{

if (NULL == p)  return false;

else if (idToDelete == p->id)

{

modifyTree (p);

return true;

}

else if (idToDelete < p->id)

return deleteNode(p->left, idToDelete);

else

return deleteNode (p->right, idToDelete);

}

void modifyTree (treePtr &p)

// p is either root or an internal pointer in the tree

// Algorithm deletes node pointed to by p.

{

treePtr temp, marker = p;

if ((NULL == p->right) && (NULL == p->left))      // leaf case

p = NULL;

else if (NULL == p->right)  // one-kid case, re-hook p to left child

p = p->left;

else if (NULL == p->left)     // other one-kid case, re-hook p to right child

p = p->right;

else     // 2-kid case

{

p = p->left;  // re-route pointer around node to be deleted

temp = p;

while (temp->right != NULL)

temp = temp->right;       // found new attachment point

temp->right = marker->right;    // re-hook branch

}

delete marker;

}