Вот, что получилось у меня:

PS Функцию myToLower() блондинка писала, что для данного задания даже в плюс)))

решила проработать, алгоритм не из форума, взяла отсюда http://www.studfiles.ru/preview/1644497/




Хоть ты тресни не понимаю правильно ли я выбрала параметры у функции и по какому принципу их нужно выбирать. Решила что void Tree::destroy(Node *node, Node *parent ), потому что наша другая функция по удалению не полинома должна передавать именно узел, который нужно удалить. Не понимаю зачем в этом алгоритме 2 параметра.

Вот эти строчки в коде мне не понятны




Ну и ,конечно,по узлу с 2 потомками завал. Можно прокомментировать каждую строчку?

Ой, не увидела, что свою написали. Я тогда вашу посмотрю и если что-то не пойму- спрошу.

Гм. Смысл выполнения поставленной перед Вами задачи - не взять готовое и как-то приладить под свои нужды, а всё-таки разобраться с тем, что и как должно происходить. Меня удручает Ваша склонность брать чей-то неизвестно как работающий и с какими ошибками код и тупо его добавлять в свой. И на первый взгляд, код с ошибками. Как Вы их будете исправлять, ничего не понимая в коде, остаётся только догадываться.

Но картинки по ссылке годные, как раз под мой право-левый вариант кода. И хотя картинка, демонстрирующая самый сложный случай

описывается как
на самом деле на рисунке всё происходит зеркально: удаляемый узел заменяется крайним левым узлом дерева из правой ветви и т.д. Выбор право-левого подхода или лево-правого подхода есть дело вкуса (иначе нужно вводить какой-то критерий выбора, например, можно оценить глубины левой и правой ветви поддерева). Но когда текст расходится с картинкой, лично у меня начинается когнитивный диссонанс. Уверен, что и в коде по ссылке есть недоработки. Стоит ли им безоглядно пользоваться?



Я тоже не понимаю смысла этой строчки. Но учитывая, что функция удаления в коде определена кака не как у Вас (без ссылки на указатель)
то какой-то смысл должен быть.



Каждую строчку - это сума сойти можно. Оно Вам точно нужно? 



Давайте лучше по моему коду.  Спрашивайте  

Добавлено через 10 минут и 38 секунд

Потому что при удалении узла нужно поправить предка этого узла, который на него указывает (либо через leftPtr, либо через rightPtr). Если этого не сделать, то все дерево посыпется - в нём будут присутствовать нерелевантные указатели (то есть указывающие куда-то, но неизвестно куда).

Разобрала удаление узла. Код закомментировала.



Вот этот кусочек кода не поняла

само условие ставит в тупик 

по моей логике условие должно было бы примерно таким(parent->p !== node) Ведь p указывает на крайний левый узел, за ним ноль. Он не может быть нашим узлом с 2 потомками.

Посмотрела void Tree::remove_non_palindroms(). Так как корень нельзя обработать рекурсивно мы его выделяем отдельно. 

Посмотрела 



Вот эта срока не понятна, почему так?
node = parent->rightPtr
node = parent->leftPtr


Еще в функции добавление узла. Вначале вроде поняла. Вот мы нашли место в дереве, где надо поставить узел. current хранит этот адрес. Потом про него нигде не упоминается. Мы начинаем опять с корня, проверяя значения ключа, и устаналиваем его в нужное место.Можно об этом поподробнее.


Это сообщение отредактировал(а) lenarano - 15.5.2015, 14:34

Спасибо за вопросы! Давайте по порядку...

Очень хорошо! Позволю себе внести правки.

Замечательно, что Вы поняли необходимость правки соответствующего указателя у предка (если он есть; если нет, то правим root) при удалении узла. Такая правка в коде удаления делается аж четыре раза, что намекает на выделение повторяющегося кода в отдельную функцию (лучше даже в inline-функцию):Все эти "можно проверить" легко реализуются через assert(). 

В результате введения в дело parentFixup() функция удаления приобретает такой вид:
Внешний вид у функции улучшился значительно. Вполне возможно, что и улучшилось понимание происходящего. Да, осталось разобрать самый тяжёлый случай с двумя потомками и его непонятками.



Простите, parent->что?

Это сообщение отредактировал(а) feodorv - 15.5.2015, 18:03

Что же делать в самом тяжелом случае удаления узла из бинарного дерева, когда у этого самого узла есть оба потомка?

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

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

Осталось собственно найти следующий элемент по отношению к удаляемому, не забывая про необходимость помнить предка этого следующего элемента:

Весь выше приведённый код легко записывается в компактную двустрочную форму:


Осталось поправить указатели:и предка удаляемого узла:


В теории всё просто. На практике Вы рано или поздно столкнётесь со случаем, когда p совпадает с node (то есть когда у node->rightPtr отсутствует левый потомок: node->rightPtr->leftPtr есть 0). Тогда вносимые в указатели правки приведут к хаосу, так как их планирование осуществлялось в предположении, что p != node (то есть что предок следующего узла не есть удаляемый узел). А что собственно меняется в коде в случае p == node? В этом случае мы должны внести всего одну правку в указатели:

• p->leftPtr править бесполезно, так как Вы правите значение у удаляемого узла (это значение канет в Лету вместе с удаляемым узлом). Более того, поправив p->leftPtr, Вы безвозвратно испортите node->leftPtr, необходимое при правке c->leftPtr.
• c->rightPtr править на node->rightPtr вообще нельзя, так как node->rightPtr есть собственно узел c. Более того, в таком случае при замене в дереве узла node на узел c значение c->rightPtr вообще править не нужно: оно какое было, таким и остаётся.
• c->leftPtr (который есть 0), нужно заменить на node->rightPtr.

Вот отсюда и код

Здесь мы правим значения p->leftPtr и c->rightPtr только в том случае, если p не есть node.

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

В принципе, вариант, когда p совпадает с node, можно выделить в особый случай среди наших if-else (так как поиск следующего элемента в дереве не нужен - этот элемент уже известен):

Можно повыпендриваться дальше и проверить ещё и node->leftPtr->rightPtr (как будто мы смотрим предыдущий узел по отношению к node, а не следующий):

PS Этот код не проверял, так что если что, не обессудьте)))

Место-то в дереве мы нашли. Но оно пустое, оно не занято ни каким другим узлом. Соответственно, current становится нулём. Посмотрите внимательно на цикл:

По его окончании current просто-напросто равен 0. Как его можно дальше использовать?


В чем же смысл этого цикла? В поиске узла (предка), в который мы будем осуществлять вставку нового узла. Смысл - в поиске parent, а не current; current здесь вспомогательная переменная. Но даже найдя этот узел, мы снова вынуждены определять ветку, в которую будем вставлять новый узел, либо в leftPtr, либо в rightPtr:
В принципе, особыми усилиями можно обойтись и без повторного определения ветки, но в данном случае это не принципиально.



  
А нельзя его обрабатывать рекурсивно, потому что у него нет предка. Мы для него не можем писать:
А вот почему мы проверяем значение root в цикле:

Во-первых, изначально дерево может быть пустым, и казалось бы это легко проверяется через if( root != 0 ). Но ведь в процессе удаления узлов дерево действительно может стать пустым (когда в нём изначально нет ни одного палиндрома). Поэтому проверку на 0 нужно делать постоянно.
Во-вторых, само значение root меняется при удалении корня дерева. При изменении корня на его место может встать узел, опять-таки не являющийся палиндромным, и его тоже нужно удалить. И так далее, пока дерево не опустеет, либо корнем не станет палиндромный узел. Поэтому и проверку на палиндромность нужно делать всё время. В результате получается очень компактный while.


Аналогично и в функции remove_non_palindroms_recursive(). В ней узел node, на самом деле, служит лишь для определения ветки (правой или левой) предка, в которой он находится. Мы бы могли с тем же успехом использовать функцию вида:
вообще не передавая указатель на node (а зачем, если мы его легко найдём согласно значению isLeft). Предок нам существенно необходим (не только как аргумент функции удаления), так как в процессе удаления его непалиндромных потомков изменяются его leftPtr и/или rightPtr. А их (как и root'а) нужно будет повторно проверять на палиндромность:

Как видите, узел node в таком варианте кода даже не понадобился. 


Для упрощения бесконечных -> можно ввести дополнительную переменную:
В ранее приведённом коде вместо temp использовалась переменная node, и только для упрощения кода, поэтому я надеюсь, что ответил на Ваш вопрос:



Это сообщение отредактировал(а) feodorv - 16.5.2015, 04:27

Спасибо огроменное.  
По добавлению узла вопросов не осталось.
По удалению узла вот эти 2 строчки не понятны в случае, если узел и p не совпадают:
 
Например, как на картинке из интернета, когда p=6, а с=4.
Предположим у нашего с (ключ4) есть справа потомок, а не ноль как на картинке. Разве у нас не теряются данные при этом? Вроде все при деле и 6 и 1, пристроены))) Если есть хвостик справа от 4, то всунули его в 4. А данные из 4 куда делись, разве при этом мы не теряем ключ и строку?


Это сообщение отредактировал(а) lenarano - 16.5.2015, 02:22

На картинке не нарисовано, но Вы представьте себе, что у 4-ки есть правое поддерево с ключом 5 (левого нет по условию нахождения самого левого узла). Что делать с 5-ой? Бросить на произвол судьбы? Нет, конечно. Перед тем, как править c->leftPtr и c->rightPtr, нужно бережно сохранить поддерево c->rightPtr, которое встаёт на место самого узла c:
Если поддерева нет (то есть c->rightPtr есть 0, то Вы просто правильно присвоите 0 левому потомку узла p). 


Вот Вам другая картинка, правда, с ошибкой (интересно, найдёте ли Вы её):

Здесь в последнем случае удаляется узел 5 (node), на место которого встаёт узел 6 ( c ), а у него есть правый потомок 7 (c->rightPtr). Что делать с 7-ой?


Далее. Вы на место узла 5 (node) вставляете узел 6 ( c ), при этом Вы должны сохранить все старые связи удаляемого узла 5. То есть теперь parent должен иметь своим потомком узел c вместо узла node, а потомками узла c (как бы новым node) должны стать соответствующие потомки удаляемого узла node:


В условных единицах этой картинки:

• Отсоединяем замещающий узел 6 от дерева:

  Цитата

  10->leftPtr = 7;

• Правим предка удаляемого узла:

  Цитата

  15->leftPtr = 6;

• Правим потомков замещающего узла:

  Цитата

  6->leftPtr = 5->leftPtr; 6->rightPtr = 5->rightPtr;

Всё, дерево свободно от узла 5, сохранив отсортированность своих узлов. Можно делать delete 5.


Я Вам специально выделил случай, когда p == node, чтобы подчеркнуть связность всех этих операций:
Но Вы упорно выделяете только правки p->leftPtr и c->rightPtr, которые не нужно совершать в случае p == node. Почему?



Это сообщение отредактировал(а) feodorv - 16.5.2015, 04:39

Ошибку нашла-художник оставил в итоге 5 на месте в (в). Я пристроила 7))) Я решила, что p->leftPtr это и есть с и боялась, что потеряем данные, а на этой картинке все поняла. 

  


До выдёргивания узла c так и было. После - уже не должно быть)))

Мне тут в голову пришла простая, по сути, мысль: если сначала удалить непалиндромные узлы из потомков узла, а лишь потом проверять сам узел на непалиндромность, то while не нужен. Да и уменьшится количество операций (то есть быстрее работать будет)