0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
1

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

27.10.2016, 13:43. Показов 9877. Ответов 7

Ребят нужно создать дерево где пользователь вводит слова, они записываются в дерево, а потом вводит слово которое хочет удалить из него. Вывести строку без этого слова.
Как реализовать з числами я понимаю, а вот со словами уже 4 сутки разобратся не могу. Может у кого-то есть подобная програма буду очень признателен. Спасибо
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.10.2016, 13:43
Ответы с готовыми решениями:

Вставка нового узла в бинарное дерево
Подскажите можно ли как-то реализовать, чтобы в консоле можно было вставлять новый узел, нахождение...

Не работает вставка узла в бинарное дерево
Кто может скажите почему при вставке 2ого элемента происходит отладка Вот последовательность чисел...

Функция поиска с включением узла в бинарное дерево
Здравствуйте! Помогите, пожалуйста, написать функцию поиска с включением узла в бинарное дерево....

Построить бинарное дерево поиска. Определить уровень узла с максимальным элементом
Из входной последовательности вещественных чисел построить бинарное дерево поиска. Определить...

7
56 / 56 / 31
Регистрация: 24.10.2016
Сообщений: 186
27.10.2016, 14:13 2
Все так же, только вместо сравнения использовать compare. Вы же используете std::string?
0
0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
27.10.2016, 22:11  [ТС] 3
Я понимаю что нужно сравнивать, но у функцию передатся int значения, вобщем не понимаю совсем, даже если строка задана уже в програме, все равно реализовать не могу
0
56 / 56 / 31
Регистрация: 24.10.2016
Сообщений: 186
27.10.2016, 22:16 4
Цитата Сообщение от Dvoryan Посмотреть сообщение
Вывести строку без этого слова.
Последовательность слов имеет значение?
0
0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
27.10.2016, 23:04  [ТС] 5
Нет
0
230 / 113 / 79
Регистрация: 17.10.2016
Сообщений: 312
28.10.2016, 00:49 6
Лучший ответ Сообщение было отмечено Dvoryan как решение

Решение

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
56 / 56 / 31
Регистрация: 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
0 / 0 / 0
Регистрация: 23.02.2016
Сообщений: 17
28.10.2016, 01:17  [ТС] 8
Парни, даже не представляете, как я вам благодарен. Огромное просто спасибо!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.10.2016, 01:17
Помогаю со студенческими работами здесь

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

Бинарное дерево из слов
Вроде разобралась в принципе заполнения обычного бинарного дерева из чисел. но как быть в...

Бинарное дерево слов
здравствуйте, моя задача звучит так : Написать программу, которая создает бинарное дерево слов,...

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru