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

Ошибка при добавлении элемента в бинарное дерево поиска - C++

Восстановить пароль Регистрация
 
turtlesergio
0 / 0 / 0
Регистрация: 28.02.2015
Сообщений: 1
20.06.2015, 17:34     Ошибка при добавлении элемента в бинарное дерево поиска #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
struct Tree
{
    Tree *left_son, *right_son;
    int head, key/*, depth*/;
};
 
Tree *tree(int *a, int left, int right)
{
    Tree *tree1 = new Tree;                                         // выделяем динамическую память
    int mid = middle(left,right);                                       // находим центральный элемент
    tree1->head = a[mid];                                           // записывает центрольный элемент в корень
    if (left != mid) 
    {
        tree1->left_son = tree(a, left, mid-1);         // рекурсивно вызываем функцию для левой ветки
    }
    if (right != mid) 
    {
        tree1->right_son = tree(a, mid+1, right);       // рекурсивно вызываем функцию для правой ветки
    }
    return tree1;
}
 
Tree *add(Tree *tree1, int key)
{
    Tree *temp_tree = new Tree; //создаем дерево
    temp_tree->head = key; //записываем в его корень добавляемый элемент
    Tree *curr_pos = tree1; //создаем дерево для прогонки, равное исходному дереву
    do
    {
        if (curr_pos->left_son != 0 && curr_pos->right_son !=0) //если элемент не лист
        {
            if(temp_tree->head < curr_pos->head)                                    // если элемент меньше проверяемого
            {
                if(curr_pos->left_son != 0)                                     // если слева не пусто
                    curr_pos = curr_pos->left_son;                                      // переходим к левой ветке
                else
                {                                                       // если слева пусто
                    curr_pos->left_son = temp_tree;                                 // записываем значение
                    curr_pos->left_son->left_son = 0;                                   // обнуляем поддеревья
                    curr_pos->left_son->right_son = 0;                                  // обнуляем поддеревья
                    break;                                              // конец добавления
                }
            }
            else                                                        // если элемент больше проверяемого
            {
                if(curr_pos->right_son != 0)                                        // если справа не пусто
                    curr_pos = curr_pos->right_son;                                     // переходим к правой ветке
                else                                                     
                {                                                       // если справа пусто
                    curr_pos->right_son = temp_tree;                                    // записываем значение
                    curr_pos->right_son->left_son = 0;                                  // обнуляем поддеревья
                    curr_pos->right_son->right_son = 0;                                 // обнуляем поддеревья
                    break;                                              // конец добавления
                }
            }
        }
        else
        {
 
        }
    } while (/*curr_pos->left_son != 0 && curr_pos->right_son !=0*/!0);
    return tree1;
}
Ошибка происходит при добавлении, на определенном шаге условие
C++
1
if(curr_pos->left_son != 0)
срабатывает неверно, и программа переходит к следующему узлу, которого нет. Иными словами, она "видит" левого потомка у узла, а этого происходить не должно. Подобной темы не нашел. Заранее благодарю

Добавлено через 1 час 11 минут
PS. Переделал функцию добавления, используя рекурсию.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void add (Tree * curr_pos, int key)
{
    if (key < curr_pos->head) 
    {
        if (curr_pos->left_son != nullptr)
            add (curr_pos->left_son, key);
        else 
        {
            Tree * tmp_tree = new Tree;
            curr_pos->left_son = tmp_tree;
        }
    }
    else
    {
        if (curr_pos->right_son != nullptr)
            add (curr_pos->right_son, key);
        else 
        {
            Tree * tmp_tree = new Tree;
            curr_pos->right_son = tmp_tree;
        }
    }
}
Проблема сохранилась - на моменте
C++
1
if (curr_pos->left_son != nullptr)
программа думает, что у узла есть левый потомок, хотя там, на самом деле, его нет (делал трассировку, у проблемного узла левый потомок равен "???", разве это не соответствует ключевому слову "nullptr"?)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.06.2015, 17:34     Ошибка при добавлении элемента в бинарное дерево поиска
Посмотрите здесь:

C++ Бинарное (двоичное) дерево поиска
C++ Бинарное дерево поиска знаков зодиака
Бинарное дерево поиска C++
Бинарное дерево поиска (удаление, добавление элемента) C++
C++ Бинарное дерево поиска C++
C++ Бинарное дерево поиска
C++ Бинарное дерево поиска
C++ Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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