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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Исправить ошибки в структуре http://www.cyberforum.ru/cpp-beginners/thread1482952.html
помогите, пожалуйста, выдает ошибки и все.. #include<iostream> #include<algorithm> #include<string> #include<deque> #include<queue> #include<stack> #include<fstream>
C++ Наследование: почему вызывается метод базового класса, а не производного? Всем привет, такой вопрос, почему вызывается в данном коде метод базового класса, а не производного (без указания ключевого слова virtual для func) class A { public: A() { cout << "create A" << endl; }; ~A() { cout << "delete A" << endl; }; void func(){ cout << "func A" << endl; }; private: http://www.cyberforum.ru/cpp-beginners/thread1482937.html
C++ Введение функций в программу(калькулятор)
Доброго времени суток! Извините но возможно мой вопрос глупым покажется, я только начала изучать с++, решил начать с самого простого набросать калькулятор. И решил сделать уравнение из x и y которое оно будет решать. Но как можно записать такие функции как: arcsin, arctg? К примеру как записать вот эту формулу в коде z-arcsin(x+1/3)-arctg(y^2) пользуясь только одним ворожением. Буду благодарен за...
Вычислить значение функции C++
3. вычислить Y=tg(x+2)+ctg²x(ctg(x+1)-tgx) при х = 30°, оформив в виде функций вычисление тангенса и котангенса.
C++ Выяснить сколько раз встречается максимальный элемент двумерного массива http://www.cyberforum.ru/cpp-beginners/thread1482900.html
2. Выяснить сколько раз встречается в массиве А максимальный элемент
C++ Проверить, есть ли в массиве А [n] числа В и С и определить, какое из чисел встречается в массиве чаще 1. Проверить, есть ли в массиве А числа В и С и определить, какое из чисел встречается в массиве чаще. подробнее

Показать сообщение отдельно
turtlesergio
0 / 0 / 0
Регистрация: 28.02.2015
Сообщений: 1
20.06.2015, 17:34     Ошибка при добавлении элемента в бинарное дерево поиска
Программа формирует бинарное дерево из отсортированного массива и добавляет в него элементы.

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"?)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 22:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru