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

Теряю ссылку на сына в узле дерева - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Считывание из текстового файла значения int http://www.cyberforum.ru/cpp-beginners/thread1311564.html
Сама задача: Задан файл целых чисел. Убрать из него числа, символьное представление которых не содержит заданной литеры - цифры. Составить программу. Есть рабочий код программы, но проблема в том что я считываю значения типа char и перевожу их в int (с помощью atoi). А нужно сделать чтобы программа из текстового файла сразу считывала значения int. Как именно это сделать я ума не приложу. ...
C++ NS Builder что это за программа? Ребят такой вопрос, учусь в Польше на факультете информатики, половину семестра не было на парах, из-за ситуации в Украине, приехал и начались колоквиумы (Зачеты), вот завтра уже зачет по информатике а мы изучаем программу NS Builder, если честно то первый раз услышал, при поиске в интернете выдает американские строительные сайты. Подскажите пожалуйста, для изучения построения алгоритмов можно... http://www.cyberforum.ru/cpp-beginners/thread1311557.html
Дана последовательность вещественных чисел, определить, являются ли они возрастающими по величине дробной част C++
Доброе время суток, прошу помощи в решении задачки, у самого ничего не выходит... Дана последовательность вещественных чисел, определить, являются ли они возрастающими по величине дробной части. вот как я пытался делать #include <math.h> #include <iostream> #include <windows.h> #include <conio.h> using namespace std;
C++ Поместить данные в динамический массив
Как запомнить char динамический массив при описе? char **map = new char * ; for (int i=0;i<sizey;i++) { map=new char ; } map = { };
C++ Блок-схема для программы на языке С++ http://www.cyberforum.ru/cpp-beginners/thread1311542.html
#include <stdio.h> #include <math.h> int main(int argc, char* argv) { double a; double b; double z; for(a=-5;a<=5;a+=0.5) for(x=-10;x<=10;x+=1) {
C++ Составьте блок-схему на языке С++ Пожалуйста помогите! #include <stdio.h> #include <math.h> int main(int argc, char* argv) { float e = 0.001; float z = 0.0; float i2, sub, subb, result = 0.0; int i, j; for (i = 1; i <= 8; i++) { i2 = pow(i, 2); подробнее

Показать сообщение отдельно
Gudsaf
103 / 14 / 3
Регистрация: 29.11.2010
Сообщений: 327

Теряю ссылку на сына в узле дерева - C++

26.11.2014, 16:35. Просмотров 176. Ответов 0
Метки (Все метки)

Привет, продолжаю нашествие на форум.. сегодня столкнулся с интересным приёмом в C#.
C#
1
2
3
4
5
6
7
8
9
10
11
private void Skew(ref Node node)
        {
                if (node.level == node.left.level)
                {
                        // rotate right
                        Node left = node.left;
                        node.left = left.right;
                        left.right = node;
                        node = left;
                }
        }
Данный код делает балансировку в АА дереве (один из случаев балансировки). Функция принимает значение узла который надо проверить, проверяет, если надо балансирует. При балансировке создаётся новый узел, потом к этому новому узлу прикрепляется всё что должно прикрепиться. Но есть одна проблема - отец перебалансированного узла не в курсе, что его сына заменили на нового (Node left) и в последующих вызовах выдаст неверную информацию. Как я понял эту проблему решает модификатор ref благодаря ему, отец тоже меняет ссылку на сына и всё становится прекрасно.

Но я пишу на C++, и думаю как организовать смену адреса у отца.. дело в том, что сыновья не ссылаются на своих предков - только лишь на своих сыновей. Пока есть одна идея как решить данную проблему - ввести дополнительное поле parent в класс Node.

Есть какие-нибудь оригинальные идеи?

Вот код автора на которого я пытаюсь равняться _http://demakov.com/snippets/aatree.cs
Так же пытаюсь что-то сделать в направления возвращаемых значений функции, но пока фигня получается:
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
Tree::Node *skew(Node *thisNode)
    {
        if (thisNode->left->_level == thisNode->_level)
        {   //сделать поворот вправо
            Node *left = new Node;
            
            //временный узел = левому узлу корня
            left = thisNode->left;
            //на место левого узла корня ставим правого сына
            thisNode->left = left->right;
            //временный узел становится вторым корнем, присоединяем к нему справа бывший корень
            left->right = thisNode;
            //ставим уровень нового корня в единицу
            left->_level = 1;
            //заменяем старый корень дерева новым корнем
            //*thisNode = *left;
            
            /*
            тут мы стабильно просераем связи от корня,
            чтобы не просрать связи будем возвращать адрес на новое поддерево и потом припиливать к отцу
            */
 
            return left;
        }
    }
изначально делал так: но так я грубо теряю связи отцов с сыновьями
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    void skew(Node *thisNode)
    {
        if (thisNode->left->_level == thisNode->_level)
        {   //сделать поворот в право
            Node *left = new Node;
 
            //временный узел = левому узлу корня
            left = thisNode->left;
            //на место левого узла корня ставим правого сына
            thisNode->left = left->right;
            //временный узел становится вторым корнем, присоединяем к нему справа бывший корень
            left->right = thisNode;
            //ставим уровень нового корня в единицу
            left->_level = 1;
            //заменяем старый корень дерева новым корнем
            *thisNode = *left;
}}
Добавлено через 1 час 43 минуты
Решил проблему методом 2ух новых переменных: да, код в стиле барокко, но всё же
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 skew(Node *thisNode)
    {
        if (thisNode->left->_level == thisNode->_level)
        {   //сделать поворот в право
 
            //обменять местами левого сына и отца
            Node *oldRoot = new Node;
            // скопировать в oldRoot содержимое бывшего корня thisNode
            *oldRoot = *thisNode;
            // на место бывшего корня вставить его прошлого левого сына
            *thisNode = *oldRoot->left;
 
            Node *tmpRightSone = new Node;
            // скопировать правого сына нового корня (бывшего левого сына)
            *tmpRightSone = *thisNode->right;
 
            //восстановить связи
            // на место правого сына нового корня вставить сам бывший корень
            thisNode->right = oldRoot;
            // сделать левым сыном прошлого корня правого сына новго корня
            *oldRoot->left = *tmpRightSone;
        }
    }
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru