#include <iostream>
#include <cstring>
struct node
{
node*left,
*right;
int key;
char value[100];
};
void insert(node** root, char* word)
{
node * new_node = new node();
strcpy(new_node->value, word);
new_node->key = 1;
new_node->left = NULL;
new_node->right = NULL;
if ((*root) != NULL)
{
if (strcmp((*root)->value, new_node->value) > 0)
{
insert(&(*root)->left, word);
}
else if (strcmp((*root)->value, new_node->value) < 0)
{
insert(&(*root)->right, word);
}
else
(*root)->key++;
}
else
{
(*root) = new_node;
}
}
void preorder(node* p) {
if (p == NULL) return;
std::cout << p->value << std::endl;
preorder(p->left);
preorder(p->right);
}
node* findNode(node* p, char * word) {
if (p == NULL || strcmp(p->value, word) == 0)
return p;
if (strcmp(p->value, word) > 0)
return findNode(p->left, word);
else
return findNode(p->right, word);
}
node* findMinNode(node* p) {
while (p->left != NULL) p = p->left;
return p;
}
node* DeleteNode(node *root, node * delnode)
{
if (root == NULL) return root;
else if (strcmp(root->value, delnode->value) > 0) root->left = DeleteNode(root->left, delnode);
else if (strcmp(root->value, delnode->value) < 0) root->right = DeleteNode(root->right, delnode);
else {
// у узла нет дочерних узлов
// просто удаляем этот узел
if (root->left == NULL && root->right == NULL)
{
delete root;
root = NULL;
}
// если есть один дочерний
// меняем на него
else if (root->left == NULL) {
node *temp = root;
root = root->right;
delete temp;
}
else if (root->right == NULL) {
node *temp = root;
root = root->left;
delete temp;
}
//если удаляемый элемент имеет двух потомков
//то нужно заменить его минимальным элементом из правого поддерева
// и рекурсивно удалить минимальный элемент из правого поддерева
else {
node *temp = findMinNode(root->right);
strcpy(root->value, temp->value);
root->right = DeleteNode(root->right, temp);
}
}
return root;
}
int main()
{
node* tree = NULL;
char line[] = "Ivan Ivanov Odessa 34 0482222222";
char word[] = "Odessa";
for (char *ptr = strtok(line, " ,!?"); ptr != NULL; ptr = strtok(NULL, " ,!?"))
{
insert(&tree, ptr);
}
// вывод дерева
preorder(tree);
// ввод слова для удаления
std::cout << "\nword for deleting: ";
//std::cin.getline(word, 50);
node* fnode = findNode(tree, word);
if (fnode)
{
std::cout << fnode->value << std::endl;
tree = DeleteNode(tree, fnode);
}
else
std::cout << "\nWord not found.\n";
std::cout << "\n";
// вывод дерева
preorder(tree);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0cmluZz4KCnN0cnVjdCBub2RlCnsKCW5vZGUqbGVmdCwKCQkqcmlnaHQ7CglpbnQga2V5OwoJY2hhciB2YWx1ZVsxMDBdOwp9OwoKdm9pZCBpbnNlcnQobm9kZSoqIHJvb3QsIGNoYXIqIHdvcmQpCnsKCW5vZGUgKiBuZXdfbm9kZSA9IG5ldyBub2RlKCk7CglzdHJjcHkobmV3X25vZGUtPnZhbHVlLCB3b3JkKTsKCW5ld19ub2RlLT5rZXkgPSAxOwoJbmV3X25vZGUtPmxlZnQgPSBOVUxMOwoJbmV3X25vZGUtPnJpZ2h0ID0gTlVMTDsKCWlmICgoKnJvb3QpICE9IE5VTEwpCgl7CgkJaWYgKHN0cmNtcCgoKnJvb3QpLT52YWx1ZSwgbmV3X25vZGUtPnZhbHVlKSA+IDApCgkJewoJCQlpbnNlcnQoJigqcm9vdCktPmxlZnQsIHdvcmQpOwoJCX0KCQllbHNlIGlmIChzdHJjbXAoKCpyb290KS0+dmFsdWUsIG5ld19ub2RlLT52YWx1ZSkgPCAwKQoJCXsKCQkJaW5zZXJ0KCYoKnJvb3QpLT5yaWdodCwgd29yZCk7CgkJfQoJCWVsc2UKCQkJKCpyb290KS0+a2V5Kys7Cgl9CgllbHNlCgl7CgkJKCpyb290KSA9IG5ld19ub2RlOwoJfQp9Cgp2b2lkIHByZW9yZGVyKG5vZGUqIHApIHsKCWlmIChwID09IE5VTEwpIHJldHVybjsKCglzdGQ6OmNvdXQgPDwgcC0+dmFsdWUgPDwgc3RkOjplbmRsOwoJcHJlb3JkZXIocC0+bGVmdCk7CglwcmVvcmRlcihwLT5yaWdodCk7Cn0KCgpub2RlKiBmaW5kTm9kZShub2RlKiBwLCBjaGFyICogd29yZCkgewoJaWYgKHAgPT0gTlVMTCB8fCBzdHJjbXAocC0+dmFsdWUsIHdvcmQpID09IDApCgkJcmV0dXJuIHA7CglpZiAoc3RyY21wKHAtPnZhbHVlLCB3b3JkKSA+IDApCglyZXR1cm4gZmluZE5vZGUocC0+bGVmdCwgd29yZCk7CgllbHNlIAoJCXJldHVybiBmaW5kTm9kZShwLT5yaWdodCwgd29yZCk7Cn0KCm5vZGUqIGZpbmRNaW5Ob2RlKG5vZGUqIHApIHsKCXdoaWxlIChwLT5sZWZ0ICE9IE5VTEwpIHAgPSBwLT5sZWZ0OwoJcmV0dXJuIHA7Cn0KCm5vZGUqIERlbGV0ZU5vZGUobm9kZSAqcm9vdCwgbm9kZSAqIGRlbG5vZGUpCnsKCWlmIChyb290ID09IE5VTEwpIHJldHVybiByb290OwoKCWVsc2UgaWYgKHN0cmNtcChyb290LT52YWx1ZSwgZGVsbm9kZS0+dmFsdWUpID4gMCkgcm9vdC0+bGVmdCA9IERlbGV0ZU5vZGUocm9vdC0+bGVmdCwgZGVsbm9kZSk7CgoJZWxzZSBpZiAoc3RyY21wKHJvb3QtPnZhbHVlLCBkZWxub2RlLT52YWx1ZSkgPCAwKSAgcm9vdC0+cmlnaHQgPSBEZWxldGVOb2RlKHJvb3QtPnJpZ2h0LCBkZWxub2RlKTsKCWVsc2UgewoJCS8vINGDICDRg9C30LvQsCDQvdC10YIg0LTQvtGH0LXRgNC90LjRhSDRg9C30LvQvtCyCgkJLy8g0L/RgNC+0YHRgtC+INGD0LTQsNC70Y/QtdC8INGN0YLQvtGCINGD0LfQtdC7CgkJaWYgKHJvb3QtPmxlZnQgPT0gTlVMTCAmJiByb290LT5yaWdodCA9PSBOVUxMKQoJCXsKCQkJZGVsZXRlIHJvb3Q7CgkJCXJvb3QgPSBOVUxMOwoKCQl9CgoJCS8vINC10YHQu9C4INC10YHRgtGMINC+0LTQuNC9INC00L7Rh9C10YDQvdC40LkgCgkJLy8g0LzQtdC90Y/QtdC8INC90LAg0L3QtdCz0L4gCgkJZWxzZSBpZiAocm9vdC0+bGVmdCA9PSBOVUxMKSB7CgkJCW5vZGUgKnRlbXAgPSByb290OwoJCQlyb290ID0gcm9vdC0+cmlnaHQ7CgkJCWRlbGV0ZSB0ZW1wOwoJCX0KCQllbHNlIGlmIChyb290LT5yaWdodCA9PSBOVUxMKSB7CgkJCW5vZGUgKnRlbXAgPSByb290OwoJCQlyb290ID0gcm9vdC0+bGVmdDsKCQkJZGVsZXRlIHRlbXA7CgkJfQoKCQkvL9C10YHQu9C4ICDRg9C00LDQu9GP0LXQvNGL0Lkg0Y3Qu9C10LzQtdC90YIg0LjQvNC10LXRgiDQtNCy0YPRhSDQv9C+0YLQvtC80LrQvtCyCgkJLy/RgtC+INC90YPQttC90L4g0LfQsNC80LXQvdC40YLRjCDQtdCz0L4g0LzQuNC90LjQvNCw0LvRjNC90YvQvCDRjdC70LXQvNC10L3RgtC+0Lwg0LjQtyDQv9GA0LDQstC+0LPQviDQv9C+0LTQtNC10YDQtdCy0LAKCQkvLyDQuCDRgNC10LrRg9GA0YHQuNCy0L3QviDRg9C00LDQu9C40YLRjCDQvNC40L3QuNC80LDQu9GM0L3Ri9C5INGN0LvQtdC80LXQvdGCINC40Lcg0L/RgNCw0LLQvtCz0L4g0L/QvtC00LTQtdGA0LXQstCwCgkJZWxzZSB7CgkJCW5vZGUgKnRlbXAgPSBmaW5kTWluTm9kZShyb290LT5yaWdodCk7CgkJCXN0cmNweShyb290LT52YWx1ZSwgdGVtcC0+dmFsdWUpOwoJCQlyb290LT5yaWdodCA9IERlbGV0ZU5vZGUocm9vdC0+cmlnaHQsIHRlbXApOwoJCX0KCX0KCXJldHVybiByb290Owp9CmludCBtYWluKCkKewoJbm9kZSogdHJlZSA9IE5VTEw7CgljaGFyIGxpbmVbXSA9ICJJdmFuIEl2YW5vdiBPZGVzc2EgMzQgMDQ4MjIyMjIyMiI7CgljaGFyIHdvcmRbXSA9ICJPZGVzc2EiOwoKCWZvciAoY2hhciAqcHRyID0gc3RydG9rKGxpbmUsICIgLCE/Iik7IHB0ciAhPSBOVUxMOyBwdHIgPSBzdHJ0b2soTlVMTCwgIiAsIT8iKSkKCXsKCQlpbnNlcnQoJnRyZWUsIHB0cik7Cgl9CgkvLyDQstGL0LLQvtC0INC00LXRgNC10LLQsAoJcHJlb3JkZXIodHJlZSk7CgoJLy8g0LLQstC+0LQg0YHQu9C+0LLQsCDQtNC70Y8g0YPQtNCw0LvQtdC90LjRjwoJc3RkOjpjb3V0IDw8ICJcbndvcmQgZm9yIGRlbGV0aW5nOiAiOwoJLy9zdGQ6OmNpbi5nZXRsaW5lKHdvcmQsIDUwKTsKCgoJbm9kZSogZm5vZGUgPSBmaW5kTm9kZSh0cmVlLCB3b3JkKTsKCWlmIChmbm9kZSkKCXsKCQlzdGQ6OmNvdXQgPDwgZm5vZGUtPnZhbHVlIDw8IHN0ZDo6ZW5kbDsKCQl0cmVlID0gRGVsZXRlTm9kZSh0cmVlLCBmbm9kZSk7Cgl9CgllbHNlCgkJc3RkOjpjb3V0IDw8ICJcbldvcmQgbm90IGZvdW5kLlxuIjsKCnN0ZDo6Y291dCA8PCAiXG4iOwoJLy8g0LLRi9Cy0L7QtCDQtNC10YDQtdCy0LAKCXByZW9yZGVyKHRyZWUpOwoKCgoJcmV0dXJuIDA7Cn0=