Binary Search Tree III
Write a program which performs the following operations to a binary search tree T by adding delete operation to B: Binary Search Tree II.
insert k: Insert a node containing k as key into T.
find k: Report whether T has a node containing k.
delete k: Delete a node containing k.
print: Print the keys of the binary search tree by inorder tree walk and preorder tree walk respectively.
The operation delete kk for deleting a given node zz containing key kk from TT can be implemented by an algorithm which considers the following cases:
1.If z has no children, we modify its parent z.p to replace z with NIL as its child (delete z).
2.If z has only a single child, we "splice out" z by making a new link between its child and its parent.
3.If z has two children, we splice out z's successor y and replace z's key with y's key.