Write a program that will implement the actions in the binary search tree "insert", "delete"; and "find" (by value). The program must process four types of requests:
ADD n — if the specified number is not yet in the tree, insert it and output the word "DONE" if — leave the tree as it was and display the word "ALREADY".
DELETE n — if the specified number is in the tree, delete it and display the word "DONE", if there is no — leave the tree as it was and display the word "CANNOT". When deleting an element that has two children, be sure to exchange the value with the maximum element of the left subtree.
SEARCH— should output the word «YES» (if the value is found in the tree) or the word "NO" (if not found). The tree does not change.
PRINTTREE — output the entire tree, always using the algorithm specified in the output format.
Input
Each input line contains one of the queries ADD n or DELETE n or SEARCH n or PRINTTREE . It is guaranteed that PRINTTREE queries will only be called when the tree is not empty. The total number of requests does not exceed 1000, of which no more 20 PRINTTREE.
requests
Output
For each request, display the response to it. For ADD, DELETE and SEARCH — the corresponding word on a separate line. For the PRINTTREE request, a tree must be displayed, necessarily according to the following algorithm:
template void print_tree(Node *p, int level)
{
if(p==NULL)
return;
print_tree(p->left, level+1);
for(int i=0; i < level; i++)
cout << ".";
cout << p->data << endl;
print_tree(p->right, level+1);
}
(Initial call to this function — print_tree(root,0).)
Examples
| # |
Input |
Output |
| 1 |
ADD2
ADD 7
ADD 5
PRINTTREE
ADD 5
DELETE 3
ADD 0
PRINTTREE
DELETE 7
PRINTTREE
|
DONE
DONE
DONE
2
..5
.7
ALREADY
CANNOT
DONE
.0
2
..5
.7
DONE
.0
2
.5
|