Есть n-мерное дерево

Хочу удалить поддерево.Для себя понял что ситуация может быть что удаляемое поддерево может быть
последним в списке указателей своего отца и может быть в любом другом месте,
тогда нужно список указателей отца на ветви копировать и заново заносить в массив указателей.
Правильно я понял как мне нужно удалить?Или есть более простой способ удаления указателей отца поддерева?



Это сообщение отредактировал(а) toxx - 28.3.2010, 21:50

Нет, если ты пользуешься указателями, то ничего никуда копировать не надо. Тем более, что у тебя вектор. Просто в деструкторе Tree напиши корректное уничтожение всех поддеревьев (delete tree), а когда нужно удалить конкретное поддерево, то просто применяй к нему delete и erase к Trees.

Нашел как пользоваться erase, но почемуто, использовал find чтобы значеие было итератор,но он отказывается работать...

toxx, для вектора можно использовать операцию сложения результата метода begin() и индекса, для получения итератора на нужный элемент. Но лучше использовать std::advance()

хмм хорошо понятно, а если я изменю структуру так


У меня уже будет не вектор(массив указателей), если мне нужно будет выполнить эту же задачу,
то мне также не нужно будет копировать указатели?т.е. простое перемещение указателей
например я нашел отца(у него нашел сына которого удалили delete'ом):

Я просто также сделал для вектора у меня была такая картина:
                                     10
                                   /     \
                               21      22
                             /
                           31
после удаления 
                                     10
                                   /     \
                        -172302     22


Это сообщение отредактировал(а) toxx - 29.3.2010, 00:36

Прежде, чем писать код, надо очень хорошо представлять себе алгоритм, который ты пытаешься реализовать. У тебя в коде написано непонятно что   
Кто такие dLevel и dItem? Что за загадочный if(prev->count%2!=0) в цикле? Что такое вообще count в узле дерева?
И что именно надо удалять - все поддерево или отдельный узел?

Я просто хотел спросить в общем)

У меня есть задача удалить поддеревья где нечетное число листьев т.е.:


я ищу нечетное число листьев:


Далее я понял что если удалять поддерево то и у отца этого поддерева исчезнет указатель на этого сына
т.е. как я понял нужно найти уровень отца

и собственно какой по номеру этот указатель

Далее я удаляю это поддерево

и Когда рекурсия идет обратно она останавливается на этом уровне

и удаляет его...
Правильно я представляю задчу?или ошибся слегка?

Поэтому я и спрашиваю если я буду присваивание указателей отца этого поддерева так

будет ли это верно, т.к. я читал что лучше скопировать указатели...

Это сообщение отредактировал(а) toxx - 29.3.2010, 14:04

Сделай деструктор у Tree
и удаляй нужные элементы из массива Trees (сначала delete Trees[i]; потом Trees.erase(Trees.begin()+i); )

Все сделал, все работает=) Спасибо
Но я тут прочитал еще раз свое задание

У меня было дерево
       10
     /    \
  21    22
  / \       \
33 32    45
/
34
После удаления оно стало
      10
     /    \
  21    22
  / \      
33 32   

Вродебы это не правильно?(просто для себя определить верно я сделал или нет)
Чтобы сделать тоже самое но только без std::vector<>
для структуры

Вроде правильно
Писать манипуляции с Trees вручную (перезаказ памяти под меньший размер и копирование туда оставшихся элементов)

Просто меня смущает то что при вот таком вводе данных
http://www.imagepost.ru/images/88/tt.jpg

Удаляет все дерево, оставляя одну вершину...

Это сообщение отредактировал(а) toxx - 29.3.2010, 21:04

Правильно удаляет - у вершины 3 потомка, что явно число нечетное. Т.ч. поддерево удаляется. До исследования поддеревьев глубже уже дело не доходит.

toxx, это уже проблемы задания, а не его реализации. Обратись к тому, кто это задание выдал.

xvr, bsa

Обращусь, спасибо за помощь.Задание действительно звучит двояко.

Всё-таки мне я думаю что задача состоит маленько в другом.
Как я делаю, думаю это очень просто.
Думаю из дерева нужно сделать что-то типа этого:
http://www.imagepost.ru/?v=88/tt_2.jpg

Думаю т.к.  у 2 нечетное кол-во нужно удалить ветку 2-5
аналогично 4-6-7-8
Поддеревом как я понимаю нужно считать всё кроме корня т.е. 2,3,4

В свете этого я решил сделать свой класс вектор и функцию для удаления элемента из произвольного места массива
Могу ли я применимо к указателям т.е. Vector<Tree*> выполнить удаление элементов 2,3?
Вот мой класс Vector и функция удаления erase:

Неправильно - у класса Vector не определен copy конструктор (и оператор присваивания). Без них конструкция  Vector<T> buf=*this; из erase сделает совсем не то, что было нужно
Что делает resize совсем не понятно, явно только что не resize вектора   

xvr
Вы имели ввиду вот это?:


А без этого тоже неплохо работало, а в чем разница с этим конструктором копирования и без него? хотя догадываюсь... но наверно не точно.


Это сообщение отредактировал(а) toxx - 30.3.2010, 21:23

стандартный конструктор скопирует указатель V и счетчик n. Таким образом, когда вызовется деструктор одного из объектов он освободит ОБЩУЮ память, поэтому, когда вызовется второй деструктор, произойдет попытка повторного освобождения, что приведет к краху программы.

И всеже никак не пойму у меня функция удаления

Есть метод у вектора удаления произвольного элемента массива

Опятьже я ищу уровень где нечетное число листьев 

Потом номер этого элемента

потом удаляю когда рекурсия дошла до уровня нужного


Но у меня не всегда получается то что нужно, в чем проблема я никак не понимаю) уже и свой класс вот написал для 
удаления из массива(походу кривоват слегка)Всёравно никак, может быть подскажете где ошибка, 
как xvr говорил я сделал, но это не решение задачи, как я понял.

Это сообщение отредактировал(а) toxx - 31.3.2010, 09:53

Тогда озвучте ПОЛНУЮ постановку задачи, ибо для того, что было озвучено это является решением

Вот такая постановка задачи, я уже писал в последнем посте 1й страницы, только там я еще с вектором разбирался своим, щас вот исправил.

В таком случае это делается так (делаю на vector<>, на массив переделайте сами, если надо)

Интересно,но это работает!Полунедельная проблема решена!Спасибо это делает то чего не делает моя процедура.
В связи с этим кодом родились вопросы:
1.Почему вы используете size_t? вместо int(в дефайне unsigned int)
2.Как работает resize у vector'a, хочу попробовать хотябы чтонить близкое сделать.
3.В чем недостатки моего erase? потомучто если тоже самое запускать, но вместо вектора использовать мой вектор ошибки памяти...
erase:

resize


Это сообщение отредактировал(а) toxx - 31.3.2010, 17:47

size_t специально предназначен для хранения размеров областей памяти. Так же как и ptrdiff_t предназначен для хранения смещений указателей. Если интересно, поищи в интернете, чем это обусловлено и какая выгода.
Кстати, size_t на 32-х битных машинах обычно uint32_t, а на 64-х битных - uint64_t. Как ты думаешь, почему?

Думаю из-за разрядности системы, как я понимаю в 32-битных и 64-битных системах один и тот же тип
занимает разное количество памяти в битах.верно?щас ищу про size_t и ptrdiff_t...

Например размер указателей различается, а размеры char, short и int нет. Размер long зависит от платформы (в 64-х битных *nix он 64 бита, а в Win64 - 32 бита, если не ошибаюсь)

Размер int может отличаться. Например Intel сомпилятор под Linux 64 имеет ключ -ilp64, который делает int,long и void* все по 64 бита (еще есть -ilp32, который их всех делает по 32)

На некоторых DSP процессорах char 2х байтовый   

Судя по статье есть смысл использовать
size_t и ptrdiff_t если ты переносишь приложения на 64х битные системы, а так написано, что на моей 32х битной
ничего не будет  заметно...

Это сообщение отредактировал(а) toxx - 1.4.2010, 15:15

Мой отец в таких случаях всегда говорит: "Делай хорошо, плохо само получится". Не известно, каким местом жизнь потом повернется.   

Проверил функцию вашу функцию xvr
Сначала у меня сложилась видимость что всё верно делает, потом сегодня я сел опять проверять, но только 
уже на других данных(увеличил количество уровней дерева до 3х, до этого проверял на одном уровне,
и увидел что если на 1м уровне 3 поддерева на втором у каждого дерева еще по 3 поддерева
и на третьем уровне еще под 1 поддереву у каждого) и понял что функция вызывается смотрит что у
второго уровня 3 поддерева и удаляет весь первый уровень не смотря на то, что есть еще 3й уровень.
Опять добавил рекурсию... менял условия, но опять ничего не выходит.
Функция remove_odd() написанная вами и рисунок дерева которое я вводил 
мой erase()


И как я ей пользуюсь:


До этого я просто в main() написал root->remove(); и понял, что это ошибка только сегодня(тестируя, всегда на 1 уровне дерева)

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

Это сообщение отредактировал(а) toxx - 2.4.2010, 16:27

Да, есть такая бага. remove_odd должна выглядеть так:

Пробовал так, если выше нечетное количество вершин она их удаляет...

Также я пробовал остановить рекурсию break; использовал но он как я понял только одну функцию
вызванную рекурсией завершает...
Также пробовал переменные вводить чтобы в условие прописывалось и он только один раз удалял на ветке.

Так и должно быть, в полном соотвествии с заданием

Может вам все же надо удалять не поддерево, а только узел? Это уже совсем другая задача.

xvr
хех, спасибо буду надеяться, что верно всё=) 

xvr
Да оказалось верно...это я видимо зря панику развёл =)
Спасибо еще раз за помощь.

ой темой ошибся..

Это сообщение отредактировал(а) toxx - 27.4.2010, 18:23