Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
0 / 0 / 0
Регистрация: 23.10.2017
Сообщений: 9
1

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

17.05.2018, 23:37. Просмотров 872. Ответов 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
440 / 327 / 171
Регистрация: 01.07.2015
Сообщений: 1,162
18.05.2018, 04:05 2
Цитата Сообщение от dishocall Посмотреть сообщение
Как я понял я выхожу за границы дерева
По-моему, ваш код просто напросто обнуляет дерево:

Цитата Сообщение от dishocall Посмотреть сообщение
if (!p) tr = NULL; //один узел
Если у удаляемого узла нет родителей, то это не обязательно значит, что остался один узел. Это также может означать, что мы удалем корень, у которого, как не странно, нет родителей.

Можете удалить нужные элементы сначала в левом и правом поддеревьях, а потом проверить корень на соответствие условию для удаление и, при необходимости, удалить.

Методом тыка нашел рабочий вариант del_odd:

C++
1
2
3
4
5
6
7
8
9
10
11
void del_odd(tree *&tr) {  //Удаление нечётных элементов из дерева
  if (tr) {
    del_odd(tr->left);
    del_odd(tr->right);
 
    if (tr->inf % 2 != 0) {
      tree *v = tr;
      Delete(tr, v);
    }
  }
}
Если все равно что-то с удалением будет не так, то попробуйте вставить условие в другие места.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.05.2018, 04:05

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

Реализация бинарного дерева поиска
Есть код, Помогите найти ошибку. using System; namespace BinarySearchTree { public...

Реализация бинарного дерева поиска
Задача: Реализация бинарного дерева поиска Компилируется нормально, а при запуске выбивает ошибку...


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

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

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