Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
yrceus
86 / 86 / 80
Регистрация: 25.08.2013
Сообщений: 338
1

Оператор присвоения в бинарном дереве

26.03.2016, 21:35. Просмотров 1243. Ответов 10
Метки нет (Все метки)

Не смог разобраться. Прокомментируйте, будьте добры.
Задание такое, определите стандартный конструктор и функции управления копированием(конструктор копии и оператор присвоения) данным двум классам:
C++
1
2
3
4
5
6
7
8
9
10
11
12
class TreeNode {
    string value;
    int count;
    TreeNode *left;
    TreeNode *right;
public: 
};
//-----------------------------------------
class BinStrTree {
    TreeNode *root;
public:
};
Вопрос, как здесь должен выглядеть оператор присвоения?(в бинарном дереве)
Он же всю связность испортит.
Пытался сделать так, чтобы присваивая, левый операнд удалялся, а правый просто записывался в конец дерева. Думал через деструктор удалять узел, все хорошо, но если узел последний, как сообщить наверх указателю чтоб сюда не показывал(nullptr)...
В отдельную функцию, но тоже самое
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
#include<iostream>
using namespace std;
class TreeNode {
    string value;
    int count;
    TreeNode *left;
    TreeNode *right;
    void erase(TreeNode*&);
public:                                                                 //стандартный конструктор
    TreeNode(string v = "", int c = 0) : value(v), count(c), left(nullptr), right(nullptr) {}
                                                                            // коструктор копии
    TreeNode(TreeNode &tim_obj) : value(tim_obj.value), count(tim_obj.count), left(nullptr), right(nullptr) 
    {
        if (tim_obj.left)
            left = tim_obj.left;
        if (tim_obj.right)
            right = tim_obj.right;
    }
    TreeNode& operator=(TreeNode &) {
              //??????????????????                   ??????????????????????
    }
    ~TreeNode() {}
};
//-----------------------------------------------------------------------
class BinStrTree {
    TreeNode *root;
public:
};
//-----------------------------------------------------------------------
int main() {    
    return 0;
}
//-----------------------------------------------------------------------
void TreeNode::erase(TreeNode *&prev) {
    TreeNode *time_ptr = right, *del;
    if (time_ptr) {
        if (time_ptr->left) {
            while (time_ptr->left->left)
                time_ptr = time_ptr->left;
            auto *pt = time_ptr->left->right;
            del = time_ptr->left;
            time_ptr->left = pt;
            del->right = nullptr;
        }
        else {
            del = time_ptr;
            right = time_ptr->right;
            del->right = nullptr;
        }
    }
    else if (left) {
        del = left;
        left = del->left;
        del->left = nullptr;
    }
    else {
        prev = nullptr;
        delete this;
        return;
    }
    value = del->value;
    count = del->count;
    delete del;
}
0
Изображения
Тип файла: png Безымянный.png (32.8 Кб, 8 просмотров)
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2016, 21:35
Ответы с готовыми решениями:

Предок в бинарном дереве
Помогите пожалуйста! Необходимо написать программу, которая для двух вершин дерева определяет,...

Поиск в бинарном дереве
Привет всем! Нужно написать код, с которым в бинарном дереве можно найти заданное пользователем...

Строки в бинарном дереве
Есть шаблонный класс бинарного дерева. Со числами он работает нормально, но при добавлении строки в...

Поиск в Бинарном Дереве!
Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента....

Разобраться в бинарном дереве
Нашел вот такой вариант построения бинарного дерева. Просьба прокомментировать строки кода...

10
kravam
быдлокодер
1715 / 902 / 106
Регистрация: 04.06.2008
Сообщений: 5,588
26.03.2016, 23:17 2
Это что за переменная, что она значит?

C++
1
TreeNode::count
1
yrceus
86 / 86 / 80
Регистрация: 25.08.2013
Сообщений: 338
27.03.2016, 08:10  [ТС] 3
По контексту, несколькими страницами ранее в книге описывался счетчик ссылок, как у интеллектуальных указателей. Хорошо, в конструктор копии его можно оформить, а оператор присваивания? Если есть узел и к нему присваиваем другой узел, из другого дерева такого же типа. Или это глупость?
0
kravam
быдлокодер
1715 / 902 / 106
Регистрация: 04.06.2008
Сообщений: 5,588
27.03.2016, 10:17 4
Цитата Сообщение от yrceus Посмотреть сообщение
Если есть узел и к нему присваиваем другой узел, из другого дерева такого же типа. Или это глупость?
Нет не глупость. Вот на рисунке я показал, как это будет выглядеть. Ничего страшного, просто следуй классическому синтаксису и присваивай полям одного узла значения полей другого узла.

Потом разобраться с count, наверное, при присвоении она должна увеличиться на 1

С этим просто разобраться. Дальше пойдёт сложнее.

++++++++++++++++++++++++++++++++++++++

Обрати внимание на рисунок. После присвоения у нас образовалось два болтающимхся в воздухе узла, A1 и A2. они занимают место в памяти и к ним никак не обратиться. Мусор, короче. При присвоении они должны удаляться. Это первое.

И второе, самое сложное, на мой взгляд, это написать удаление узлов. Допустим, после присвоения A0 = B0 ты захочешь удалить узел A0 из дерева B0. Тут нужно, наверное, писать отдельную функцию удаления delete. И она должна уметь удалить A0 из A, но не из B. Для этого, наверное, и нужна переменная count, чтобы знать, сколько узлов ссылаются на удаляемый узел. Естессно, не забывать, что при удалении узла и дочернии узлы должны удаляться тоже. В общем, удаление узлов- самая сложная часть.
1
Изображения
Тип файла: jpg bt.jpg (35.8 Кб, 2 просмотров)
27.03.2016, 10:17
yrceus
86 / 86 / 80
Регистрация: 25.08.2013
Сообщений: 338
27.03.2016, 10:26  [ТС] 5
Все понял! Единственный вопрос, на рисунке нижнее левое дерево, после присваивания. Там же с большой долей вероятности синяя ветка(новая) да и узел А0 с новыми значениями будут не упорядочены. То есть, если значение В0 вовсе будет намного меньше самого корня. Понимаете, вся новая синяя ветка будет не доступна, ее не найти, или вообще ошибка будет. Присваивая мы же не обращаем внимание на упорядочивание.
0
Mr.X
Эксперт С++
3195 / 1722 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
27.03.2016, 10:43 6
Цитата Сообщение от yrceus Посмотреть сообщение
Все понял! Единственный вопрос, на рисунке нижнее левое дерево, после присваивания. Там же с большой долей вероятности синяя ветка(новая) да и узел А0 с новыми значениями будут не упорядочены. То есть, если значение В0 вовсе будет намного меньше самого корня. Понимаете, вся новая синяя ветка будет не доступна, ее не найти, или вообще ошибка будет. Присваивая мы же не обращаем внимание на упорядочивание.
Так у вас по условию упорядоченное дерево или нет? Если упорядоченное, то для него присвоение узлов нарушает порядок, поэтому должно быть запрещено.
1
yrceus
86 / 86 / 80
Регистрация: 25.08.2013
Сообщений: 338
27.03.2016, 11:04  [ТС] 7
Да по условию у меня свобода энтузиазму))) И тут же именно бинарное дерево, левые и правые потомки, оно же только упорядоченное. Или поправьте)
Вот, а удалить элемент, уже просто очень интересно. Алгоритм удаления из упорядоченного бинарного дерева, в сети нашел вот такой. Прокомментируйте, правильно ли я его понял:
0
Изображения
Тип файла: jpg Безымянный11.jpg (60.2 Кб, 3 просмотров)
Тип файла: png Безымянный1.png (27.0 Кб, 1 просмотров)
yrceus
86 / 86 / 80
Регистрация: 25.08.2013
Сообщений: 338
27.03.2016, 11:22  [ТС] 8
Ищем у правого потомка самый левый, его значение переписываем в исходный, удаляем, а правую ветку цепляем на место удаленного.

Добавлено через 15 минут
Вообще то, да, оно может быть не упорядоченное, возможны другие условия связи... Значит если упорядоченное, оператор копирования удалять.
C++
1
TreeNode& operator=(TreeNode&) = delete;
Добавлено через 40 секунд
А если нет, то просто копировать)
0
kravam
быдлокодер
1715 / 902 / 106
Регистрация: 04.06.2008
Сообщений: 5,588
27.03.2016, 11:32 9
Лучший ответ Сообщение было отмечено yrceus как решение

Решение

Цитата Сообщение от yrceus Посмотреть сообщение
Присваивая мы же не обращаем внимание на упорядочивание.
Да, а надо бы, что-то я не подумал. Упорядочивание не в том смысле, что больше-меньше, а в том, что всегда после кучи приваиваний можно было бы построить красивые двумерные деревья без петель. Навскидку если- значения одного узла можно присваивать другому только в том случае, если они находятся в РАЗНЫХ ДЕРЕВЬЯХ. Для этого в каждом узле необходимо завести какой-то массив переменных, что ли. Например, узел A принадлежит нескольким деревьям с номерами 0,2,3,6. Тогда в узле A должен быть такой массивчик:

C++
1
2
3
4
5
6
7
8
class TreeNode {
    string value;
    int count;
    TreeNode *left;
    TreeNode *right;
    array  int [0,2,3,6];
public: 
};
Узел B пусть принадлежит деревьям с номерами 1,3,8. Тогда вот узел B

C++
1
2
3
4
5
6
7
8
class TreeNode {
    string value;
    int count;
    TreeNode *left;
    TreeNode *right;
    array  int [1,3,8];
public: 
};
При присвоении A==B эти массивы [0,2,3,6] и [1,3,8] нужно проверять, есть ли в них одинаковые элементы. Ага, есть элемент 3. То есть узел A и узел B принадлежат одному и тому же дереву с номером 3 и присвоение A==B делать нельзя. Как-то так. Если это реализовывать, то count, быть и может, и не нужна вовсе! По моему разумению она просто-напросто количество деревьев, к которым принадлежит узел. А это количество легко вычислить как размер массива array.
1
Mr.X
Эксперт С++
3195 / 1722 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
27.03.2016, 16:22 10
Цитата Сообщение от yrceus Посмотреть сообщение
Да по условию у меня свобода энтузиазму)))
Ну тогда, учитывая, что по условию допускается присвоение узлов, дерево у вес неупорядоченное, так что не надо выдумывать то чего нет, и что противоречит условию.
1
kravam
быдлокодер
1715 / 902 / 106
Регистрация: 04.06.2008
Сообщений: 5,588
30.03.2016, 21:07 11
Мне тут вопрос задали, правилен ли алгоритм удаления узла из бинарного дерева на рисунке. Вот интересно, автор сам не видит что ли, что В КОРНЕ НЕПРАВИЛЬНЫЙ? Что там может быть правильного-то?

Я просто увидел, что узел 1 убрали, а вместо него поставили узел 2, который- внимание- дочерний узла 1. Гениально, чё сказать. И это ВИДНО, что самое интересное.

Надо делать так: удаляем узел 1- значит удаляем из дерева и все его дочерние узлы. В том числе и узел 2. То есть всей этой свадьбы, которая справа на втором рисунке быть не должно. Нет узла N1- нет ничего, что лежит правее корневого узла. Всё.

+++++++++++++++++++++++++++++++++++++++++++

Но учитывая, что мы решили, что можно значения узлов присваивать друг другу, узел 1 МОЖЕТ остаться на рисунке, даже в случае его удаления. Просто нужно понять, что теперь нет просто операции "удалить узел N 1". А есть такие операции:

"удалить узел N 1 из дерева A"
"удалить узел N 1 из дерева B"

То есть смысл в том, что у нас запросто может быть НЕСКОЛЬКО деревьев. И узел 1 может принадлежать 2-м из них, дереву A и дереву B. Это-то и нужно рассматривать! Так вот, мы можем удалить узел N1 из дерева A, но на рисунке он может остаться, если принадлежит ещё и другому дереву, то есть дереву B

+++++++++++++++++++++++++++++++++++++++++++

А на рисунке видно, что узел N1 принадлежит одному дереву. Так не пойдёт. Если говорим о присваивании, значит имеем несколько деревьев- не можем же мы присваивать значения узлов друг другу, в пределах одного и того же дерева! Получатся петли. Так что ищи другой рисунок, для двух деревьев минимум. А лучше сам думай. А этот рисунок для одного, да и тот неправильный.
1
30.03.2016, 21:07
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.03.2016, 21:07

Сумма элементов в бинарном дереве
Требуется реализовать функцию(void findSum(); ) которая определить сумму цифр в значениях тех...

Удалить узел в бинарном дереве
Добрый вечер. В задании нужно найти узел дерева с наибольшим показателем счетчика, после чего...

Функция поиска в бинарном дереве
Я понимаю как реализовать эту функцию если в бинарном дереве хранятся обычные числа(последовательно...


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

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

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