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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Dvoryan
0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
#1

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

27.10.2016, 13:43. Просмотров 271. Ответов 7

Ребят нужно создать дерево где пользователь вводит слова, они записываются в дерево, а потом вводит слово которое хочет удалить из него. Вывести строку без этого слова.
Как реализовать з числами я понимаю, а вот со словами уже 4 сутки разобратся не могу. Может у кого-то есть подобная програма буду очень признателен. Спасибо
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.10.2016, 13:43     Бинарное дерево из слов и удаление узла
Посмотрите здесь:
C++ Бинарное дерево из слов
Бинарное дерево подклассов основного класса-узла. Доступ к подклассам по указателю - объекту класса-родителя C++
Бинарное дерево. Удаление звена C++
C++ Бинарное дерево, удаление элемента
Принцип добавления слов в бинарное дерево C++
Бинарное дерево поиска (удаление, добавление элемента) C++
Построить бинарное дерево поиска получающееся в результате вставки ключевых слов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OlafNestandart
53 / 53 / 20
Регистрация: 24.10.2016
Сообщений: 186
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
53 / 53 / 20
Регистрация: 24.10.2016
Сообщений: 186
27.10.2016, 22:16     Бинарное дерево из слов и удаление узла #4
Цитата Сообщение от Dvoryan Посмотреть сообщение
Вывести строку без этого слова.
Последовательность слов имеет значение?
Dvoryan
0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
27.10.2016, 23:04  [ТС]     Бинарное дерево из слов и удаление узла #5
Нет
John999
223 / 106 / 49
Регистрация: 17.10.2016
Сообщений: 312
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
53 / 53 / 20
Регистрация: 24.10.2016
Сообщений: 186
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++ Вставка узла в дерево Windows Explorer
C++ Реализовать 2-3 дерево с добавлением и удалением узла
Бинарное дерево C++
Бинарное дерево C++

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru