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

Некорректное удаление элемента бинарного дерева поиска

18.04.2017, 22:34. Просмотров 496. Ответов 2
Метки нет (Все метки)

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

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

Удаляется совсем не то, что нужно. Помогите, пожалуйста, пофиксить данный баг.

Код дерева



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
#include <iostream>
#include <Windows.h>
using namespace std;
////////////////////////////////////////////////////////////////////////////
 
struct Node
{
    int info, level = 0;
    Node *left, *right;
};
///////////////////////////////////////////////////////////////////////////
 
void GoToXY(short x, short y)
{
    HANDLE StdOut = GetStdHandle(STD_OUTPUT_HANDLE);
    COORD coord = { x, y };
    SetConsoleCursorPosition(StdOut, coord);
}
///////////////////////////////////////////////////////////////////////////
 
void PRINT(Node *&MyTree, short x, short y, int level, char c)
{
    if (MyTree)
    {
        if (level > 0 && c != 'k')
        {
            if (c == 'l') x -= 5;
            else x += 5;
        }
        else if (c != 'k')
            if (c == 'l') x -= 7;
            else x += 7;
 
            GoToXY(x, y += 2);
            level--;
            cout << MyTree->info;
            PRINT(MyTree->left, x, y, level, 'l');
            PRINT(MyTree->right, x, y, level, 'r');
    }
}
///////////////////////////////////////////////////////////////////////////
 
void del(Node *&Tree)
{
    if (Tree != NULL)
    {
        del(Tree->left);
        del(Tree->right);
        delete Tree; 
    }
}
///////////////////////////////////////////////////////////////////////////
 
void add_node(int info, Node *&MyTree)
{
    if (MyTree == NULL)
    {
        MyTree = new Node;
        MyTree->info = info;
        MyTree->left = MyTree->right = NULL;
    }
 
    if (info < MyTree->info)
    {
        if (MyTree->left != NULL) add_node(info, MyTree->left);
        else
        {
            MyTree->left = new Node;
            MyTree->left->left = MyTree->left->right = NULL;
            MyTree->left->info = info;
            MyTree->level += 1;
        }
    }
 
    if (info > MyTree->info)
    {
        if (MyTree->right != NULL) add_node(info, MyTree->right);
        else
        {
            MyTree->right = new Node;
            MyTree->right->left = MyTree->right->right = NULL;
            MyTree->right->info = info;
            MyTree->level += 1;
        }
    }
}
/////////////////////////////////////////////////////////////////////////
 
void sort(Node *&MyTree)
{
    system("cls");
    while (MyTree->right != NULL)
    {
        MyTree = MyTree->right;
        cout << MyTree->info << endl;
        if (MyTree->right == NULL)
        {
            cout << "Deleting.. " << MyTree->info << endl;
            MyTree->right = NULL;
        }   
    }
}
///////////////////////////////////////////////////////////////////////
int main()
{
    Node *Tree = NULL;
    int x = 80, y = 10;
    int kod, info, key = 1;
    while (true)
    {
        cout << "1 - ADD; 2 - PRINT; 3 - SORT; 4 - CLEAR WINDOW 0 - CLEAR AND OUT" << endl;
        cin >> kod;
        switch (kod)
        {
        case 1:
            cout << "Input the number: " << endl;
            while (key != 666)
            {
                cin >> info; add_node(info, Tree);
                key = info;
            }
            key = 0;
            break;
        case 2: PRINT(Tree, x, y, Tree->level, 'k'); y = 10; x = 80; cout << "\n\n\n\n\n"; break;
        case 3: sort(Tree->left->right); PRINT(Tree, x, y, Tree->level, 'k'); y = 10; x = 78; cout << "\n\n\n\n"; break;
        case 4: system("cls"); break;
        case 0: del(Tree); exit(1);
        }
    }
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.04.2017, 22:34
Ответы с готовыми решениями:

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

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

удаление элемента бинарного дерева
как удалить элемент бинарного дерева,имеющий 2 потомка?(например дерево (2)-(7 и 0)-(4 и...

Удаление элемента из бинарного дерева
Ругается компилятор в Visual Studio при выполнении кода удаления элемента, а именно в том месте,...

2
1118 / 931 / 429
Регистрация: 25.12.2016
Сообщений: 3,030
18.04.2017, 23:15 2
Цитата Сообщение от sryv Посмотреть сообщение
Но после удаления и вывода обновленного дерева получается какая-то несуразица.
А где происходит удаление? Если в функции del, то она удаляет всё дерево.
0
0 / 0 / 0
Регистрация: 25.02.2017
Сообщений: 11
19.04.2017, 18:35  [ТС] 3
likehood, удаление происходит в функции sort, которая находит максимальный элемент в левом поддереве и удаляет его
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.04.2017, 18:35

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

Удаление элемента из сбалансированого бинарного дерева
Задание: написать программу, которая создает сбалансированное бинарное дерево, написать процедуру,...

Реализовать удаление элемента бинарного дерева
Подскажите пожалуйста, нужен метод, который удаляет элемент( и возвращает этот элемент) из...

Итератор дерева бинарного поиска
Если у нас в качестве коллекции выступают вектора, очереди, стеки и т.п. то там вроде бы всё...

Создание бинарного дерева поиска
Людииииии помогите пож-таааа.....Нужно создать бинарное дерево поиска, считывая элементы из текст...


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

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

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