Форум программистов, компьютерный форум CyberForum.ru

Бинарное дерево из слов и удаление узла - C++

Восстановить пароль Регистрация
 
Dvoryan
0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
27.10.2016, 13:43     Бинарное дерево из слов и удаление узла #1
Ребят нужно создать дерево где пользователь вводит слова, они записываются в дерево, а потом вводит слово которое хочет удалить из него. Вывести строку без этого слова.
Как реализовать з числами я понимаю, а вот со словами уже 4 сутки разобратся не могу. Может у кого-то есть подобная програма буду очень признателен. Спасибо
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OlafNestandart
12 / 12 / 4
Регистрация: 24.10.2016
Сообщений: 62
27.10.2016, 14:13     Бинарное дерево из слов и удаление узла #2
Все так же, только вместо сравнения использовать compare. Вы же используете std::string?
Dvoryan
0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
27.10.2016, 22:11  [ТС]     Бинарное дерево из слов и удаление узла #3
Я понимаю что нужно сравнивать, но у функцию передатся int значения, вобщем не понимаю совсем, даже если строка задана уже в програме, все равно реализовать не могу
OlafNestandart
12 / 12 / 4
Регистрация: 24.10.2016
Сообщений: 62
27.10.2016, 22:16     Бинарное дерево из слов и удаление узла #4
Цитата Сообщение от Dvoryan Посмотреть сообщение
Вывести строку без этого слова.
Последовательность слов имеет значение?
Dvoryan
0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
27.10.2016, 23:04  [ТС]     Бинарное дерево из слов и удаление узла #5
Нет
John999
73 / 73 / 35
Регистрация: 17.10.2016
Сообщений: 214
28.10.2016, 00:49     Бинарное дерево из слов и удаление узла #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#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[100];
    char word[50];
 
    std::cout << "Enter string:\n";
    std::cin.getline(line, 100);
    for (char *ptr = strtok(line, " ,!?"); ptr != NULL; ptr = strtok(NULL, " ,!?"))
    {
        insert(&tree, ptr);
    }
    // вывод дерева
    preorder(tree);
 
    // ввод слова для удаления
    std::cout << "\nEnter word for deleting\n: ";
    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";
 
    // вывод дерева
    preorder(tree);
 
    return 0;
}
проверка
http://ideone.com/s5dtCK
OlafNestandart
12 / 12 / 4
Регистрация: 24.10.2016
Сообщений: 62
28.10.2016, 01:02     Бинарное дерево из слов и удаление узла #7
А я вот так сделал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <string>
#include <locale>
 
using namespace std;
 
class BTree {
public:
    BTree(): root(nullptr) {}
    void add(string& data) {
        makeNode(&root, data);
    }
    void del(string& data) {
        deleteNode(&root, data);
    }
 
    void print() {
        printNode(root);
        cout << endl;
    }
 
private:
    struct Node {
        Node(): left(nullptr), right(nullptr) {}
        string data;
        Node *left, *right;
    };
 
    void deleteNode(Node** node, string& data) {
        if (*node) {
            if ((*node)->data.compare(data) == 0) {
                Node *n = *node;
                if (!n->left && !n->right)
                    *node = nullptr;
                else if (!n->left)
                    *node = n->right;
                else if (!n->right)
                    *node = n->left;
                else {
                    *node = n->right;
                    Node** ptr = node;
                    while (*ptr) ptr = &((*ptr)->left);
                    (*ptr) = n->left;
                }
                delete(n);
                deleteNode(node, data);
            } else {
                deleteNode(&((*node)->left), data);
                deleteNode(&((*node)->right), data);
            }
        }
    }
 
    void makeNode(Node** node, string& data) {
        if (!(*node)) {
            Node* newNode = new Node;
            newNode->data = data;
            *node = newNode;
        } else {
            if ((*node)->data.compare(data) < 0)
                makeNode(&((*node)->left), data);
            else if ((*node)->data.compare(data) > 0)
                makeNode(&((*node)->right), data);
        }
    }
 
    void printNode(Node* node) {
        if (node) {
            printNode(node->right);
            cout << node->data << " ";
            printNode(node->left);
        }
    }
 
    Node *root;
};
 
int main() {
    BTree tree;
    string str;
    int choice;
    setlocale(LC_ALL, "");
    while (true) {
        cout << "Выберите действие:" << endl;
        cout << "1. Сохранить слово" << endl;
        cout << "2. Удалить слово" << endl;
        cout << "3. Показать все слова" << endl;
        cout << "4. Выход" << endl;
        cin >> choice;
        if (choice == 1) {
            cout << "Введите слово: ";
            cin >> str;
            tree.add(str);
        } else if (choice == 2) {
            cout << "Введите слово: ";
            cin >> str;
            tree.del(str);
        } else if (choice == 3) {
            tree.print();
        } else {
            break;
        }
    }
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.10.2016, 01:17     Бинарное дерево из слов и удаление узла
Еще ссылки по теме:

Построить бинарное дерево поиска получающееся в результате вставки ключевых слов C++
C++ Бинарное дерево
C++ Бинарное дерево из слов

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Dvoryan
0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
28.10.2016, 01:17  [ТС]     Бинарное дерево из слов и удаление узла #8
Парни, даже не представляете, как я вам благодарен. Огромное просто спасибо!
Yandex
Объявления
28.10.2016, 01:17     Бинарное дерево из слов и удаление узла
Ответ Создать тему

Метки
c++, бинарное дерево, дерево, узлы
Опции темы

Текущее время: 01:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru