Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Числовое значение string в int https://www.cyberforum.ru/ cpp-beginners/ thread2248190.html
Привет! Такая задача: задается строка, из неё нужно среди всех значений, идущих до введённой точки вычленить все цифры и составить из них наибольшее число. Я завёл массив из 10 элементов, и решаю...
Поле динамический массив состоящий из объектов-потомков класса C++
Всем привет, интересует такой вопрос: Есть базовый класс, от которого наследуется другие классы, можно ли в качестве поля базового класса использовать динамический массив, состоящий из...
C++ Перевод программы из Pascal в C++
Добрый вечер, нужна помощь! Буду благодарен. Сама задача звучит так : Найти значение выражения (2*5!+3*8!) / (6!+4!) где n! означает факториал числа п (n! = 1 • 2 • ... • n). (Определить функцию...
C++ Цикл while без тела Доброго времени суток. Искал быструю сортировку массива из чисел типа int. Наткнулся на такое: void quick_sort( int * start, int * en ) { if( start != en ) { int * left = start;... https://www.cyberforum.ru/ cpp-beginners/ thread2248183.html
C++ Дано два двухзначных числа. Найти число, у которого сумма цифр больше https://www.cyberforum.ru/ cpp-beginners/ thread2248178.html
Дано два двухзначных числа. Найти число, у которого сумма цифр больше. Если сумма цифр этих чисел одинаковая, то вывести большее из заданных чисел. Входные данные: Во входном потоке через пробел...
C++ Сумма ряда без циклов (через рекурсию)
Учусь работать с рекурсией, и застрял на самой реализации суммы через рекурсию без циклов. Задание во вложении // Lab7.cpp: определяет точку входа для консольного приложения. // #include...
В каждой строке все элементы, не равные нулю, переписать в начало строки, а нулевые элементы – в конец массива C++
Дан двумерный массив. В каждой строке все его элементы, не равные нулю, переписать (сохраняя порядок) в начало строки, а нулевые элементы – в конец массива. Новый массив не заводить.
C++ Перевести код с Си на Си++ #include <stdio.h> #include <locale.h> #include <math.h> int main(void) { double x, eps; double n; double y1, y2; short k; https://www.cyberforum.ru/ cpp-beginners/ thread2248159.html
C++ Перевести с Pascal на C++ https://www.cyberforum.ru/ cpp-beginners/ thread2248152.html
Заранее благодарю uses crt; const max=10; function sum(a:integer):integer; var b,s:integer; begin b:=abs(a); s:=0;
C++ Парсинг IPv4 Написал функцию для парсинга IPv4. И не соображу как надо переделать условия, что бы if (_it == _end) не висело как апендикс в конце цикла? Потому что делает почти все тоже, что и под Метка 1 ... https://www.cyberforum.ru/ cpp-beginners/ thread2248151.html
0 / 0 / 0
Регистрация: 23.10.2017
Сообщений: 9
0

Удаление нечетных чисел из дерева бинарного поиска

17.05.2018, 23:37. Просмотров 912. Ответов 1
Метки (Все метки)

Задача: Удалить нечетные числа из дерева бинарного поиска.
Вообщем, ошибка в функции удаления нечетных. Как я понял я выхожу за границы дерева. Как исправить?
Функция удаления нечетных:
C++
1
2
3
4
5
6
7
8
9
10
void del_odd(tree *&tr) {  //Удаление нечётных элементов из дерева
    if (tr) {
        if (tr->inf % 2 != 0) {
            tree *v = tr;
            Delete(tr, v);
        }
            del_odd(tr->left);
            del_odd(tr->right);
    }
}
Весь код:
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include<iostream>
 
using namespace std;
 
struct tree {
    int inf;
    tree *left;
    tree *right;
    tree *parent;
};
 
tree *node(int x) { 
    tree *n = new tree;
    n->inf = x;
    n->left = n->right = NULL;
    n->parent = NULL;
    return n;
}
 
void insert(tree *&tr, int x) { 
    tree *n = node(x);
    if (!tr) tr = n;  
    else {
        tree *y = tr;
        while (y) {  
            if (n->inf > y->inf) 
                if (y->right)
                    y = y->right;
                else {
                    n->parent = y; 
                    y->right = n;
                    break;
                }
            else if (n->inf < y->inf) 
                if (y->left)
                    y = y->left;
                else {
                    n->parent = y;
                    y->left = n;
                    break;
                }
        }
    }
}
 
tree *find(tree *tr, int x) { 
    if (!tr || x == tr->inf) 
        return tr;
    if (x < tr->inf)
        return find(tr->left, x); 
    else
        return find(tr->right, x); 
}
 
tree *Min(tree *tr) {
    if (!tr->left) return tr;
    else return Min(tr->left);
}
 
tree *Max(tree *tr) {
    if (!tr->right) return tr;
    else return Max(tr->right);
}
 
tree *Next(tree *tr, int x) {
    tree *n = find(tr, x);
    if (n->right)
        return Min(n->right);
    tree *y = n->parent;
    while (y && n == y->right) {
        n = y;
        y = y->parent;
    }
    return y;
}
 
void Delete(tree *&tr, tree *v) {//удаление узла
    tree *p = v->parent;
    if (!p) tr = NULL; //один узел
    else if (!v->left && !v->right) { //нет детей
        if (p->left == v)
            p->left = NULL;
        if (p->right == v)
            p->right = NULL;
        delete v;
    }
    else if (!v->left || !v->right) { //если тоько один ребёнок
        if (!p) {
            if (!v->left) {
                tr = v->right;
                v->parent = NULL;
            }
            else {
                tr = v->left;
                v->parent = NULL;
            }
        }
        else {         //если есть правый ребёнок
            if (!v->left) {
                if (p->left == v)
                    p->left = v->right;
                else
                    p->right = v->right;
                v->right->parent = p;
            }
            else {
                if (p->left == v)
                    p->left = v->left;
                else
                    p->right = v->left;
                v->left->parent = p;
            }
            delete v;
        }
    }
    else {           //есть оба ребёнка
        tree *succ = Next(tr, v->inf);
        v->inf = succ->inf;
        if (succ->parent->left == succ) {
            succ->parent->left = succ->right;
            if (succ->right)
                succ->right->parent = succ->parent;
        }
        else {
            succ->parent->right = succ->right;
            if (succ->right)
                succ->right->parent = succ->parent;
        }
        delete succ;
    }
}
 
void inorder(tree *tr) { 
    if (tr) {
        inorder(tr->left);
        cout << tr->inf << " ";
        inorder(tr->right);
    }
}
 
void del_odd(tree *&tr) {  //Удаление нечётных элементов из дерева
    if (tr) {
        if (tr->inf % 2 != 0) {
            tree *v = tr;
            Delete(tr, v);
        }
            del_odd(tr->left);
            del_odd(tr->right);
    }
}
 
int main() {
    setlocale(LC_ALL, "rus");
    int n, x;
    cout << "n = "; cin >> n;
    tree *tr = NULL;
    for (int i = 0; i < n; i++) {
        cout << i << ": ";
        cin >> x;
        insert(tr, x);
    }
 
    del_odd(tr);
    inorder(tr);
    cout << endl;
    system("pause");
    return 0;
}


Вернуться к обсуждению:
Удаление нечетных чисел из дерева бинарного поиска
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.05.2018, 23:37
Готовые ответы и решения:

Удаление элементов из бинарного дерева (не дерево поиска)
Задание заключается в создании бинарного дерева, из букв введенной строки, обходе дерева и удалении...

Некорректное удаление элемента бинарного дерева поиска
Задача состоит в том, чтобы удалить максимальный в левом поддереве элемент и все его порожденные...

Удаление элемента из двоичного бинарного дерева поиска
Здравствуйте! Подскажите пожалуйста, как удалить элемент из двоичного бинарного дерева поиска,...

Удаление элемента из бинарного дерева поиска (bst)
Есть структура данных bst с методом delete (и некоторыми другими, не имеющими отношения к данной...

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