Форум программистов, компьютерный форум CyberForum.ru

Функция удаления элемента из дерева, ошибка в коде - C++

Восстановить пароль Регистрация
 
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
02.06.2013, 11:10     Функция удаления элемента из дерева, ошибка в коде #1
Добрый вечер, уважаемые программисты!
Помогите, пожалуйста, понять где здесь ошибка.

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
static bool h = false;
 
// узел дерева
struct Tree
{
    int znachlist; // значение узла\листа
    int balance; // фактор баланса: высота правого поддерева - высота левого
    Tree *left, *right; // левое и правое поддерево
};
 
void search_and_delete (int *sel,Tree** rr);
void Balance_R(Tree** rr);
void Balance_L(Tree** rr);
void deldel(Tree** q);
 
void main()
{
    setlocale(0,"");
    h = false;
    int* sdf = new int; // элемент, который будет удалять
    cout << "\n\nкакой элемент удаляем?\n";
    cin >> *sdf;
    search_and_delete(sdf,&root);
    delete sdf;
 
    cin.get();
    cin.get();
}
 
 
// поиск и удаление элемента
void search_and_delete (int *sel,Tree** rr)
{
    //h = false; // изначально устанавливаем флаг как "высота не изменилась"
    Tree **q;  //сохранение указателя на удаляемый узел
    Tree **w; // указатель на узел "левый из правых"
    //h = false;
    if (*rr == NULL)
    {
        cout << "Такого удаляемого элемента в дереве нет";
    }
    else
    {
        if (*sel < (*rr)->znachlist)
        {
            search_and_delete (sel,&(*rr)->left); //далее  по левому поддереву
            if (h==true)
            {
                Balance_L(&(*rr));
            }
        }
        else
        {
            if (*sel > (*rr)->znachlist)
            {
                search_and_delete (sel,&(*rr)->right); //далее  по правому поддереву
                if (h==true)
                {
                    Balance_R(&(*rr));
                }
            }
            else // нашли нужный нам элемент
            {
                q=rr; // q - хранит в себе адрес "удаляемого элемента"
                //место ошибки?
                if ((*rr)->right==NULL) // у удаляемого узла имеется только левое поддерево, тогда
                {
                    *rr=(*rr)->left;
                    h=true;
                }
                else
                {
                    if ((*rr)->left==NULL) // у удаляемого узла есть только правое поддерево
                    {
                        *rr=(*rr)->right;
                        h=true;
                    }
                    else // у удаляемого узла есть два поддерева (леов еи правое)
                    {
                        deldel (q);
                        if (h==true)
                        {
                            Balance_L(&(*rr));
                        }
                    }
                }
                delete q;
            }
        }
    }
}
 
 
void deldel (Tree **q)
{//выполняем поиск самого правого узла в левом поддереве
    Tree** w=q;
    if ((*w)->right != NULL)//спуск по правому поддереву
    {
        deldel (&(*w)->right);
    }
    if (h==true)
    {
        Balance_R(w); //возврат по пути спуска по правому поддереву и, если нужно, балансировка
    }
    else //заменяем значения удаляемого и самого правого в левом поддереве
    {
        (*q)->znachlist=(*w)->znachlist;
        *q=*w;
        *w=(*w)->left; // у самого правого элемента может быть левый лист, поэтому нужно поднять этот левый лист на месте переносимого узла
        h=true;
    }
}

Ошибка возникает, когда проводим функцию delete q. Уходим куда-то в бесконечность.
Может быть ошибка в функции void deldel(Tree** q); ?

Пожалуйста, помогите разобраться с ошибкой))))

Добавлено через 27 минут
upp))

Добавлено через 1 час 24 минуты
Пожалуйста, помогите с ошибкой

Добавлено через 13 часов 14 минут
upp
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Perfecter
1 / 1 / 0
Регистрация: 29.05.2012
Сообщений: 11
02.06.2013, 11:21     Функция удаления элемента из дерева, ошибка в коде #2
Я вот что-то у тебя объявления root не вижу.
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
02.06.2013, 11:29  [ТС]     Функция удаления элемента из дерева, ошибка в коде #3
Ой, оно в мэйне есть, случайно с этого кода удалила:

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
void main()
{
    setlocale(0,"");
    int i;
    Tree *root = NULL; // указатель на корень дерева равен NULL
    for (i=0; i<20; i++)
    {
        int* asas = new int; // вводимое значение для дерева
        cin >> *asas;
        search_and_add(asas, &root);
        delete asas;
    }
    printWithLvls (root,0);
    
 
    h = false;
 
    int* sdf = new int; // элемент, который будет удалять
    cout << "\n\nКакой элемент удаляем?\n";
    cin >> *sdf;
    search_and_delete(sdf,&root);
    delete sdf;
 
    printWithLvls (root,0);
 
    cin.get();
    cin.get();
}

Проблема в том, что я просматриваю через точки останова, и выходит вот такая штука: нашли удаляемый элемент, заменили значения, всё шик и блеск и когда функция (search_and_delete) выходит к своему самому-самому концу, она пишет:

Необработанное исключение в "0x77e415de" в "функция удаления авл дерево.exe": 0xC0000005: Нарушение прав доступа при чтении "0xfeeefefa".
что делать и как быть?

Я уже думаю, что пробелма в указателях, т.е., когда нужно удалить листик, а значение родителя и листика после выполнения функции (по алгоритму) совпадают, может указатели не меняются, и пограмма удаляет родителя, а не листик? А если удаляет листик, то чего ж она "не обрабатывает" что-то там.... В общем, это единственная проблема и мне бы очень хотелось её решить.
Perfecter
1 / 1 / 0
Регистрация: 29.05.2012
Сообщений: 11
02.06.2013, 11:43     Функция удаления элемента из дерева, ошибка в коде #4
А в какой именно строке пишет ? + Если не сложно, не могли бы вы привести весь код ?

Добавлено через 3 минуты
C++
1
delete q
Попробуйте
C++
1
delete (*q)
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
02.06.2013, 11:58  [ТС]     Функция удаления элемента из дерева, ошибка в коде #5
Perfecter, вы знаете, кажется, я нашла "где именно идёт ошибка".
т.е., у меня есть функция вывода дерева, когда пишет про ошибку, то выводит ту функцию. Я уже заменила "переменные", но он всё равно указывает на функцию печати.

И уже пишет про "там ошибка, тааааам".

И правда там. Удалила я, значит, в конце эту "функцию печати того, что получилось" и что? Вроде бы дерево "удалило", но мне не проверить, удалило оно или нет. Т.е., программа работает корректно, но без итогового вывода. хм-хм-хм, что делать?)))


Вот

специфический красивый вывод дерева помог таки найти "причину ошибки"))

Да, я была права. Значит проблема ошибки такая допустим, у меня есть дерево, и я удаляю в середине элемент, который является "узлом" с двумя детками. Всё бы ничего, но вот мой вывод печати показал: правую половину распечатал, дошёл до корня, напечатал корень, а когда надо бы дойти до след. элемента, который мы удаляли, он и пишет про ошибку, всё-таки это была проблема с указателями из тех функций.
Yandex
Объявления
02.06.2013, 11:58     Функция удаления элемента из дерева, ошибка в коде
Ответ Создать тему
Опции темы

Текущее время: 00:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru