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

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

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

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

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

Ребят нужно создать дерево где пользователь вводит слова, они записываются в дерево, а потом вводит слово которое хочет удалить из него. Вывести строку без этого слова.
Как реализовать з числами я понимаю, а вот со словами уже 4 сутки разобратся не могу. Может у кого-то есть подобная програма буду очень признателен. Спасибо
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.10.2016, 13:43
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Бинарное дерево из слов и удаление узла (C++):

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру - C++
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру. вот...

Бинарное дерево из слов - C++
Вроде разобралась в принципе заполнения обычного бинарного дерева из чисел. но как быть в случае,если дерево необходимо заполнить...

Бинарное дерево подклассов основного класса-узла. Доступ к подклассам по указателю - объекту класса-родителя - C++
Короче, необходимо сделать бинарное дерево, решающее арифметическое выражение, предварительно туда записанное. Есть основной класс...

Бинарное дерево. Удаление звена - C++
Помогите реализовать функцию удаления звена дерева Del (все потомки и само звено нужно удалить). Пытался реализовать немного, но потомков...

Бинарное дерево, удаление элемента - C++
Задание: создать класс для хранения целых чисел в виде бинарного дерева. Обеспечить поиск, добавление и удаление элементов. Получилось...

Принцип добавления слов в бинарное дерево - C++
Доброго времени суток! Я хотел бы узнать по какому принципу добавлять слова в бинарное дерево. Если работать с числами, то принцип понятен,...

7
OlafNestandart
54 / 54 / 20
Регистрация: 24.10.2016
Сообщений: 186
27.10.2016, 14:13 #2
Все так же, только вместо сравнения использовать compare. Вы же используете std::string?
0
Dvoryan
0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
27.10.2016, 22:11  [ТС] #3
Я понимаю что нужно сравнивать, но у функцию передатся int значения, вобщем не понимаю совсем, даже если строка задана уже в програме, все равно реализовать не могу
0
OlafNestandart
54 / 54 / 20
Регистрация: 24.10.2016
Сообщений: 186
27.10.2016, 22:16 #4
Цитата Сообщение от Dvoryan Посмотреть сообщение
Вывести строку без этого слова.
Последовательность слов имеет значение?
0
Dvoryan
0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
27.10.2016, 23:04  [ТС] #5
Нет
0
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
1
OlafNestandart
54 / 54 / 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;
}
1
Dvoryan
0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
28.10.2016, 01:17  [ТС] #8
Парни, даже не представляете, как я вам благодарен. Огромное просто спасибо!
0
28.10.2016, 01:17
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.10.2016, 01:17
Привет! Вот еще темы с ответами:

Бинарное дерево поиска (удаление, добавление элемента) - C++
Задачи В Бинарном дереве поиска 1)введено с клавиатуры значение, если существует узел с таким значением, он удаляется; 2) с...

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

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой - C++
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Дерево с приведенной структурой узла - C++
Дерево с приведенной структурой узла Что это такое? Как реализовать функцию, которая вернет указатель на начало линейного списка,...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

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