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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Почему выводится пустая очередь? http://www.cyberforum.ru/cpp-beginners/thread1835856.html
Выводится пустая очередь. В чем ошибка? struct Queue { int item; Queue *next; }*Pbeg=NULL, *Pend=NULL; void queueFeel() { int size = 0; cout << "Сколько элементов будет в вашей очереди?"...
C++ Определить количество школьников, которым достанется яблок меньше, чем некоторым из их товарищей Пожалуйста, понимаю, что кому-то это легко, но уже запуталась.... �� школьников делят �� яблок “поровну”, то есть так, чтобы количество яблок, доставшихся любым двум школьникам, отличалось бы не... http://www.cyberforum.ru/cpp-beginners/thread1835849.html
C++ Точка пересечения отрезка и плоскости
Есть отрезок с координатами концов p1(x0,y0,z0) и p2(x1,y1,z1), есть плоскость, для простоты - ортогональная плоскость XZ, то есть это простой прямоугольник вида: var p1 = Qt.vector4d(12.0, 0.0,...
Перегрузка функции С++ C++
Создайте перегруженную функцию decr(), которая от аргумента вычитает 1, где аргументы целый (int), вещественный (double) тип, символьный (char) тип. Память под числа (объекты) выделяется динамически....
C++ Написать программу, используя метод дихотомии http://www.cyberforum.ru/cpp-beginners/thread1835802.html
Задание: Написать программу на языке С++, используя метод дихотомии (половинного деления). xn=-1; xk=3.5; f1(x)=e^arcsin(0.02x)+x^3-2.5; f2(x)=2-0.8x Вот код: #include <iostream> #include...
C++ Найти наименьший номер члена последовательности удовлетворяющий условию Найти наименьший номер члена последовательности П.5.18.Правил Запрещено размещать задания и решения в виде картинок и других файлов с их текстом. Редактор формул внизу страницы подробнее

Показать сообщение отдельно
John999
223 / 106 / 49
Регистрация: 17.10.2016
Сообщений: 312
28.10.2016, 00:49
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
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru